在陣列中找到的最小唯一編號

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 

如果積分值的有限範圍，則可以與由值索引BitArrays更換HashSets。

Answer 2

你不需要做完整的排序。執行冒泡排序內部循環，直到你在一端得到不同的最小值。在最好的情況下，這將具有時間複雜度O（k * n），其中k =非明顯最小值的數目。但最壞的情況複雜度是O（n * n）。所以，當期望值爲k時，這可以是高效的。

我認爲這應該是儘可能小的時間複雜度，除非您可以將任何O（n * logn）排序算法適應上述任務。