找出給定數(shù)組 不在數(shù)組中的最小的那個(gè)數(shù)字

 給定一個(gè)數(shù)組，其內(nèi)容是一些隨機(jī)的、不重復(fù)的正整數(shù)，如：

{4, 23, 1, 8, 9, 21, 6, 12}

要求找出不在數(shù)組中出現(xiàn)的最小的那個(gè)數(shù)，比如這個(gè)數(shù)組中未在數(shù)組中出現(xiàn)的最小值是：2

這個(gè)問(wèn)題實(shí)際應(yīng)用的原型可以是一個(gè)ID分配系統(tǒng)，其使用一個(gè)數(shù)組來(lái)保存已分配的ID，每次回收就從數(shù)組中刪除一個(gè)元素(O(n))，而分配則需要找到最小的那個(gè)可用的ID，就是這個(gè)算法要做的事情。

這個(gè)問(wèn)題從naive的解法到快速的解法的思路轉(zhuǎn)換是十分巧妙的，當(dāng)然，如果之前沒(méi)有接觸過(guò)類似的題，注意到這個(gè)特性應(yīng)該不是一件很容易的事。

設(shè)數(shù)組為A，大小為n，下標(biāo)從1開始，下面是一系列逐步改進(jìn)的算法：

一、窮舉查找

一般的問(wèn)題都可以通過(guò)這種很暴力的方式來(lái)做，從1到n逐個(gè)判斷是否在數(shù)組中：

MIN-AVAILABLE-NUM(A, n)

　　for i = 1 to n

　　　　do if i not in A

　　　　　 then return i

return n+1

顯然，這里的算法復(fù)雜度是O(n^2)

二、先排序再二分查找

第一種方法，每次查找都是線性查找，要改進(jìn)最先想到的自然是二分查找，二分查找的前提是有序， 所以：

先排序，用O(nlgn)的快速排序、歸并排序或者堆排序；因?yàn)閿?shù)組中的元素是一些自然數(shù)，我們甚至可以使用O(n) 的基數(shù)排序，當(dāng)然，需要更多的內(nèi)存。
對(duì)1..n進(jìn)行判斷，復(fù)雜度也為O(nlgn)
所以，整體的算法復(fù)雜度為O(nlgn)

三、該數(shù)組的一個(gè)特性

其實(shí)仔細(xì)觀察該數(shù)組A[1]..A[n]，我們可以得出一個(gè)結(jié)論：如果該數(shù)組中存在未被使用的數(shù)，那么Max(A) > n。

證明很簡(jiǎn)單，假設(shè)Max(A) <= n，由于該數(shù)組大小為n，那么該數(shù)組中的元素只能是從1到n的某個(gè)排列，從而得出該數(shù)組中不存在未被使用的數(shù)，矛盾。

這個(gè)特性和抽屜原理有些類似之處。

從而我們可以有另外一個(gè)方法：

先排序
再利用該特性搜索
MIN-AVAILABLE-NUM(A, n)

　　for i = 1 to n

　　　　do A[i] > i

　　　　　 then return i

return n+1



注意到，如果我們使用基數(shù)排序，可以將復(fù)雜度降低到O(n)。

四、一個(gè)線性時(shí)間，線性空間的算法

第三個(gè)算法雖然能達(dá)到理論意義上的O(n)，但是基數(shù)排序隱含的常數(shù)因子較大，而且不是原地排序，這里給出一個(gè)不需要排序的算法：

MIN-AVAILABLE-NUM(A, n)

　　for i = 1 to n

　　　　do if i < n

　　　　　 then B[i] = 1

　　　　　 else B[i] = 0

for i = 1 to n

　　　　if(B[i] == 0) return i;

　　 return n+1;

這里使用一個(gè)輔助數(shù)組B來(lái)表示1到n這些數(shù)是否存在在數(shù)組A中，只要不存在就將其標(biāo)為0，最后在B中找到第一個(gè)值為0的便是我們要找的那個(gè)元素；如果B中元素全為1，這說(shuō)明A使用了所有1到n這些數(shù)，那么返回的便是下一個(gè)n+1.

此處無(wú)須排序，且復(fù)雜度為O(n)，但需要一個(gè)額外的O(n)的數(shù)組。

五、一個(gè)線性時(shí)間、常數(shù)空間的算法

利用快速排序的原理，我們可以在不使用額外數(shù)組的情況下達(dá)到O(n)的效率，原理為：

取1到n的中間值m = (1 + n)/2，用m將數(shù)組分成A1, A2兩個(gè)部分，A1中的元素全部小于等于m，A2中的元素全部大于m（注意此處用的是下標(biāo)，而不是A[m]），如果A1的大小為m，則空閑元素在A2中，這在前面證明過(guò)，然后就在A2中應(yīng)用同樣的方法。

MIN-AVAILABLE-NUM(A, low, up)

　　if(low == up) return low

　　m = (low + up) / 2

　　split = partition(A, low, up, m)

　　if a[split] == m

　　 then return MIN-AVAILABLE-NUM(A, low, split)

else return MIN-AVAILABLE-NUM(A, split+1, up)

這里遞歸式為：T(n) = T(n/2) + O(n)，根據(jù)主定理的第三種情況，復(fù)雜度為O(n)，其實(shí)也就是一個(gè)等比數(shù)列：n + n/2 + n/4...