Haskell:在线性时间内找到不在列表中的最小非负整数,仅使用列表

Question

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

(这想出了这里.)

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)]是相关的.我们可以丢弃剩余的元素.使用这个想法,我们可以实现线性时间分而治之的解决方案.不像在归并排序,在递归的每一步,我们递归到只有一个 2子列表每一个最多原来的一半大小(后做一些线性主持工作).这给出了线性时间复杂度.

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等.通过一次完成所有这一切,可以相当容易地优化它.然而,这仍然是一个线性时间解决方案,我想让代码更清晰,而不是优化常数因素.

这个问题和解决方案不是我原来的; 当我学习Haskell时,我在课堂上遇到过它.