求线性时间内不在列表中的最小非负整数，只使用列表

Question

考虑一个函数minout :: [Int] -> Int，它接受一个非负整数的列表，并返回列表中不存在的最小的非负整数。如果输入有重复项，函数的行为并不重要。这可以在线性时间内实现，只使用列表(没有数组或向量或其他具有有效随机访问的数据结构)?

(This came up here)

Answer 1

如果l包含0和(length l) - 1之间的所有数字，则minout l为length l，否则位于[0..(length l - 1)]。所以minout l总是在[0..(length l)]中，只有l中的元素在[0..(length l - 1)]中才是相关的。我们可以抛弃剩下的元素。利用这个思想，我们可以实现一个线性时间分治的解决方案。与归并排序不同，在递归的每一步，我们只递归到两个子列表中的一个，每个子列表的大小最多是原始列表的一半(在做了一些线性工作之后)。这给出了线性时间复杂度。

minout :: [Int] -> Int
minout = minoutaux 0
    where
    minoutaux :: Int -> [Int] -> Int -- list base -> smallest integer >= base not occuring in list
    minoutaux base [] = base
    minoutaux base [x] = base + (if x==base then 1 else 0)
    minoutaux base xs = if (length smallpart == n2) then  minoutaux (base+n2) bigpart else minoutaux base smallpart
        where
        n = (length xs)
        n2 = n `div` 2
        smallpart = [x | x <- xs , base <= x , x < base + n2]
        bigpart = [x | x <- xs, base + n2 <= x, x < base + n]

在上面的代码中，minoutaux是一个函数，它给出一个"基数"整数和一个具有不同条目的列表，返回最小的整数，这个整数至少是基数，并且不出现在列表中。为了做到这一点，它丢弃了可以丢弃的"不相关"元素，如前所述，并生成两个列表，由位于[base, base + n2)(称为smallpart)和[base + n2, base + n)(称为bigpart)的数字组成。每个列表的长度最多为n2。如果length smallpart == n2，则smallpart包含了[base, base + n2)中的所有数字，因此答案一定在bigpart中，否则，smallpart本身存在"空白"，因此答案在smallpart中。

为什么它在线性时间内运行?首先，整个长度为N的链表被遍历几次，这需要10N次操作。然后在一个更小的列表上调用minoutaux，该列表的大小最多为N/2。所以我们(最多)有10N/2个操作。然后是10N/4, 10N/8，以此类推。把这些加起来，我们得到10(2N) = 20N。(常量10只是一个例子)

在这里，我们多次遍历列表来计算它的长度，计算smallpart，计算bigpart，等等。通过一次完成所有这些操作，可以很容易地对其进行优化。然而，这仍然是一个线性时间解决方案，我想使代码更清晰，而不是优化常数因素。

这个问题和解决方案不是我的原创;

Answer 2

Richard Bird在他的《函数式算法设计的珍珠》一书的第一章中描述了这个问题。(这一章正好是亚马逊上的预览版。)