查找数组中的最小唯一编号

Question

数组中的最小唯一编号定义为 min{v|v occurs only once in the array} :例如,{1,4,1,2,3}的最小唯一编号为2.有没有比排序更好的方法？

Answer 1

我相信这是时间和空间上的O(N)解决方案:

HashSet seenOnce;     // sufficiently large that access is O(1)
HashSet seenMultiple; // sufficiently large that access is O(1)

for each in input // O(N)
    if item in seenMultiple
        next
    if item in seenOnce
        remove item from seenOnce
        add to item seenMultiple
    else
        add to item seeOnce

smallest = SENTINEL
for each in seenOnce // worst case, O(N)
    if item < smallest
        smallest = item

如果您具有有限的整数值范围,则可以使用由该值索引的BitArray替换HashSet.