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

在陣列中的最小唯一號碼被定義爲 min{v|v occurs only once in the array} 例如，最小唯一編號{1,4，1，2，3}爲2 是否有任何比排序更好嗎？在陣列中找到的最小唯一編號

2012-08-14 shilk

「更好」的意思是「更低的時間複雜度」？ – 2012-08-14 01:57:58

@VaughnCato：是的，我想我們能否比O（nlogn）做得更好。 – shilk 2012-08-14 02:00:38

您的數值範圍是有限還是限制？如果它們與限制範圍不可分割，我相信O（N）是可能的。 – walrii 2012-08-14 02:04:45

相信這是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。

來源

2012-08-14 02:30:39 walrii

這是所有偉大的先生，但我在哪裏可以找到這個神奇的O（1）隨機訪問哈希函數？就我（以及世界其他地方）而言，散列函數的「最佳」隨機訪問時間是O（logn）。 – ElKamina 2012-08-14 03:39:55

除非我錯過了一些東西，否則不需要隨機訪問。第一遍循環遍歷'input'（O（N）），並在散列集上進行查找，插入和刪除，每個O（1）。總計：O（N）。第二遍現在寫在'seenOnce'上，但很容易修復：再次循環輸入（O（N）），測試'seenOnce'（O（1））的成員關係，如果它附加了它到一個新的'seenOnceList'（O（1）），總的O（N）。最後對最小值O（N）進行掃描。淨O（N），不是？ – DSM 2012-08-14 04:10:15

@ElKamina - 你用一個散列混淆了一棵樹。請參閱http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions並查看O（1）下的列表。使用大型表格和適當的散列函數，衝突並不重要。 – walrii 2012-08-14 05:47:38

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

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

來源

2012-08-15 18:32:52 PermanentGuest

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

回答

相關問題