查找O（nlogn）和O（logn）附加空間中的最小正數

這是一個衆所周知的問題的稍微修改版本，但我似乎無法弄清楚這一點。查找O（nlogn）和O（logn）附加空間中的最小正數

我們給出了一個大小爲n的數組，其中包含沒有重複的正數的未排序序列。我試圖找到數組中不包含的最小正數，但我無法以任何方式對數組進行排序或編輯。整個事情應該在O（nlogn）時間和O（logn）空間複雜度。

我能想到的所有解決方案都是多項式時間複雜度。

2016-11-08 mathew7k5b

[簡單的面試問題變得越來越難：給定數字1..100，找到缺少的數字]（http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder -given-numbers-1-100-find-the-missing-numbe） –

只需掃描數組並更新最小值，如果遇到小於當前最小值的數字。 O（n）時間和O（1）空間 – SomeWittyUsername

@SomeWittyUsername可能更仔細地閱讀問題。 – Kittsil

你可以通過在答案上進行二進制搜索而不用修改數組來解決這個問題。請記住，我們正在尋找最小的正整數，即數組中的而不是。這意味着答案不能大於n + 1，因爲我們的數組中只有n個數字。所以我們只需要在1和n + 1之間進行二進制搜索來找到我們的答案。

在我們的二進制搜索中，我們想回答這個問題：對於給定的數字k，數組中包含的每個整數1到k是什麼？因爲沒有重複，我們可以通過計算數組中小於或等於k的元素數來解決這個問題。如果計數是k，那麼每個這樣的整數都在我們的數組中;否則，至少缺少一個。

所以我們進行二分法搜索，找到上面屬性爲false的k的最小值。二進制搜索需要O（log n）次迭代，每次迭代需要O（n）次，總共需要O（n log n）次。空間實際上是O（1），因爲我們所需要的只是一個用於計數的變量。

來源

2016-11-09 00:06:50 Neal

二進制搜索需要對數組進行排序 –

正確，但我們不是二進制搜索數組。我們對最終答案進行二分搜索。 – Neal

因此，您掃描一次數組以找到最大和最小數字，然後在它們之間進行二分搜索？ –

查找O（nlogn）和O（logn）附加空間中的最小正數

回答

相關問題