在《算法新解》的前言中,我们只给出了使用分而治之策略的线性时间O(n),常数空间O(1)的解法。这里我们给出另外两种命令式解法,它们都可以达到同样的性能。

首先我们先回顾一下书中讨论的一个重要性质

1 <= answer <= n + 1

其中n是序列的长度,当原始序列是1到n的某个排列时,答案为n+1。

鸽笼排序[1]

任何基于比较的排序都会将时间性能降低到O(n lg n),所以诸如堆,排序二叉树这类的解法无法满足要求。我们可以将第i个元素x放置到它“应该”在的位置上:也就是第x个位置。如果x比n大,根据上面的公式,我们知道它一定不是答案,因此可以跳过它不做处理。否则,我们将第i个元素和第x个元素交换。由于我们交换到第i个位置上的元素不一定等于i,因此需要不断重复交换直到第i个元素比n大或者等于i。我们从1到n对i进行迭代,处理所有元素。由于每个元素仅被交换一次,因此这一处理是线性时间的(你能严格证明这一结论么?)。

接下来,我们再次扫描一遍这一序列,如果在任何位置i上,元素值不等于i,我们就找到了最终的答案。否则,说明原始序列是“满”的,我们返回n+1作为最小可用元素。

下面是一个C风格的C++例子代码。

int findMinFree1(vector<int> nums) {
    int i, n = nums.size();
    for (i = 0; i < n; ++i)
        while (nums[i] <= n && nums[i] != i + 1)
            swap(nums[i], nums[nums[i] - 1]);
    for (i = 0; i < n; ++i)
        if (i + 1 != nums[i])
            return i + 1;
    return n + 1;
}

符号编码

不论是使用一个标记数组,还是将每个元素放置到“正确”的位置上,我们本质上是想知道一个元素是否存在。存在与否是一种二值化(binary)信息。我们可以将其编码为数字的正负号。思路是如果元素x存在于序列中,我们就将第x个元素从正数反转为负数。当我们把所有不大于n的元素的正负号都反转完,我们可以再从左向右扫描一遍序列,找到第一个正数,它所在的位置就是最终的答案。

下面是这一方法的C风格的C++例子代码:

int findMinFree2(vector<int> nums) {
    int i, k, n = nums.size();
    for (i = 0; i < n; ++i)
        if ((k = abs(nums[i])) <= n)
            nums[k - 1] = - abs(nums[k - 1]);
    for (i = 0; i < n; ++i)
        if (nums[i] > 0)
            return i + 1;
    return n + 1;
}

[1] https://en.wikipedia.org/wiki/Pigeonhole_sort