给定一个数组，找出不在数组中的最小的那个数字

来源:原文链接

---

这是在TL讨论中Liu xinyu给出的一个例子，觉得思路挺有启发的，所以整理记录一下。
给定一个数组，其内容是一些随机的、不重复的正整数，如：
{4, 23, 1, 8, 9, 21, 6, 12}
要求找出不在数组中出现的最小的那个数，比如这个数组中未在数组中出现的最小值是：2
这个问题实际应用的原型可以是一个ID分配系统，其使用一个数组来保存已分配的ID，每次回收就从数组中删除一个元素(O(n))，而分配则需要找到最小的那个可用的ID，就是这个算法要做的事情。
这个问题从naive的解法到快速的解法的思路转换是十分巧妙的，当然，如果之前没有接触过类似的题，注意到这个特性应该不是一件很容易的事。
设数组为A，大小为n，下标从1开始，下面是一系列逐步改进的算法：
一、穷举查找
一般的问题都可以通过这种很暴力的方式来做，从1到n逐个判断是否在数组中：
MIN-AVAILABLE-NUM(A, n)
for i = 1 to n
do if i not in A
   then return i
      return n+1
显然，这里的算法复杂度是O(n^2)
二、先排序再二分查找
第一种方法，每次查找都是线性查找，要改进最先想到的自然是二分查找，二分查找的前提是有序， 所以：

1. 先排序，用O(nlgn)的快速排序、归并排序或者堆排序；因为数组中的元素是一些自然数，我们甚至可以使用O(n) 的基数排序，当然，需要更多的内存。
2. 对1..n进行判断，复杂度也为O(nlgn)

所以，整体的算法复杂度为O(nlgn)
三、该数组的一个特性
其实仔细观察该数组A[1]..A[n]，我们可以得出一个结论：如果该数组中存在未被使用的数，那么Max(A) > n。
证明很简单，假设Max(A) <= n，由于该数组大小为n，那么该数组中的元素只能是从1到n的某个排列，从而得出该数组中不存在未被使用的数，矛盾。
这个特性和抽屉原理有些类似之处。
从而我们可以有另外一个方法：

1. 先排序
2. 再利用该特性搜索

MIN-AVAILABLE-NUM(A, n)

for i = 1 to n

do A[i] > i

   then return i

      return n+1

注意到，如果我们使用基数排序，可以将复杂度降低到O(n)。
四、一个线性时间，线性空间的算法
第三个算法虽然能达到理论意义上的O(n)，但是基数排序隐含的常数因子较大，而且不是原地排序，这里给出一个不需要排序的算法：
MIN-AVAILABLE-NUM(A, n)
for i = 1 to n
B[i] = 0
for i = 1 to n
do if A[i] < n
   then B[A[i]] = 1
      for  i = 1 to n
if(B[i] == 0) return i;
return n+1;
这里使用一个辅助数组B来表示1到n这些数是否存在在数组A中，只要不存在就将其标为0，最后在B中找到第一个值为0的便是我们要找的那个元素；如果B中元素全为1，这说明A使用了所有1到n这些数，那么返回的便是下一个n+1.
此处无须排序，且复杂度为O(n)，但需要一个额外的O(n)的数组。
五、一个线性时间、常数空间的算法
利用快速排序的原理，我们可以在不使用额外数组的情况下达到O(n)的效率，原理为：
取1到n的中间值m = (1 + n)/2，用m将数组分成A1, A2两个部分，A1中的元素全部小于等于m，A2中的元素全部大于m（注意此处用的是下标，而不是A[m]），如果A1的大小为m，则空闲元素在A2中，这在前面证明过，然后就在A2中应用同样的方法。
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)，根据主定理的第三种情况，复杂度为O(n)，其实也就是一个等比数列：n + n/2 + n/4...