最小的非負數不在可能重複的數字列表中

這是[1]的變體。我有一個N的列表（已知數值N是非負整數）。列表的上限是1024.什麼是不在列表中的最小非負整數？。最小的非負數不在可能重複的數字列表中

對於離，這個名單可以是0,3,6,2,4,1,8,0,9,0 - 那麼輸出必須爲5

我想這樣做的方式這 - 我知道列表的長度不會> 1024.所以我有一個大小爲1024的數組IFLAG - 然後我掃描N個數字 - 如果第i個數字是k，我設置IFLAG [k] = 1 。我還保留列表中最高數字的標籤，例如MAX

在掃描列表中的所有N個數字後，我將IFLAG從1掃描到（MAX + 1），並用0標識第一個位置。是我需要的輸出。

我必須反覆做這個（數千甚至數百萬次） - 所以，有沒有更好的方法來做到這一點（可能）？我可以做到這一點，而不使用IFLAG陣列？

感謝雷伊

爲了確保我理解正確，「列表的上限是1024」和「我知道列表的長度不會> 1024」。你是說，最大列表長度和上限「k」是1024？ –

在我看來，IFLAG的大小是由列表中的最大值而不是列表的長度限定的。無論如何，如果您無法對列表的排列方式作出任何假設，您必須至少檢查一次列表中的每個項目。你的算法只檢查一次每個項目，因此就列表長度而言效率不高（你的算法在列表長度上是O（n）） –

你可以更精確地瞭解什麼是輸入，以及上限是指什麼？ –

你的方法是有效的。

它只能改善空間複雜性。

I.e.而不是數組使用變量int並設置相應的位。
然後檢查哪一位沒有設置。你已經找到了缺失的數字

2012-01-23 10:11:44 Cratylus

如果它幾乎排序，你可以排序它在O（n）insertion sort，然後找到O（n）中第一個缺失的整數。

2012-01-23 13:53:15 jgroenen

回答