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

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

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

Answer 2

您不需要进行完全排序。执行冒泡排序内循环，直到在一端获得明显的最小值。在最好的情况下，这将具有时间复杂度 O(k * n)，其中 k = 非不同最小值的数量。然而，最坏情况的复杂度是 O(n*n)。因此，当 k << n 的预期值时，这可能是有效的。

我认为这将是可能的最小时间复杂度，除非您可以使任何 O(n * logn) 排序算法适应上述任务。

Answer 3

使用字典的 Python 版本。
时间复杂度 O(n) 和空间复杂度 O(n)：

from collections import defaultdict
d=defaultdict(int)
for _ in range(int(input())):
    ele=int(input())
    d[ele]+=1
m=9999999
for i in d:
    if d[i]==1 and i<m:
        m=i
print(m if m!= 9999999 else -1)

请告诉我是否有更好的方法。