找出最小的失蹤人數在一個陣列

可能重複：
Find the Smallest Integer Not in a List 找出最小的失蹤人數在一個陣列

我被問過這個問題在接受採訪時

給定一個排序的數組，找到最小的數那是缺失的。假設所有數字都是正數。

輸入= {4,2,1,3,678,3432}

輸出= 5

排序這是我的第一種方法。我的第二種方法是有一個布爾標誌數組。第二種方法佔用大量空間。

有沒有比這更好的方法？

來源

2012-06-22 user2434

另一種方法是使用最小堆。從給定的數字構造最小堆。從counter = 1開始。刪除元素，即1. elementDeleted == Counter。遞增計數器繼續刪除第二個元素2.再次計數器== elemetnDeleted。繼續到計數器！= elementDeleted – Sandeep

假設給定數組的長度爲N。您可以使用布爾標記方法，但不需要考慮大於N的數字，因爲它們顯然太大而不能影響答案。你也可以考慮一個bitmap來節省一些空間。

來源

2012-06-22 12:53:19 unkulunkulu

+1這也可以得到 - 時間複雜度爲O（N），內存複雜度爲O（N）。我不認爲有更好的解決方案。 –

@izomorphius，在評論中的鏈接問題中有一個非常有趣的答案。 – unkulunkulu

我有一個使用桶排序的答案，但最壞的情況下，需要infite內存。這是一個更好的解決方案。 – acattle

的替代解決方案unkulunkulu的是以下內容：

k := 1 
Make an array of 2^k booleans, all initially set to false 
For every value, V, in the array: 
    if V < 2^k then: 
    set the V'th boolean to true 
Scan through the booleans, if there are any falses then the lowest one indicates the lowest missing value. 
If there were no falses then increment k and go to step 2.

這將爲O運行（N日誌或多個）時間和O（S）的空間，其中，n是輸入陣列和s的大小是最小值不存在。通過不重新檢查連續迭代中的最低值，可以提高效率，但不會改變約束條件。

來源

2012-06-22 19:47:16

找出最小的失蹤人數在一個陣列

回答

相關問題