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

Question

数组中的最小唯一数定义为 min{v|v 在数组中只出现一次例如，{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

如果您的整数值范围有限，您可以将 HashSets 替换为按值索引的 BitArrays。