{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ò)類(lèi)似的題，注意到這個(gè)特性應(yīng)該不是一件很容易的事。
設(shè)數(shù)組為A，大小為n，下標(biāo)從1開(kāi)始，下面是一系列逐步改進(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è)特性和抽屜原理有些類(lèi)似之處。
從而我們可以有另外一個(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...
喜歡 
頂
難過(guò)
囧
圍觀
無(wú)聊
