考虑一个函数minout :: [Int] -> Int,它接受一个不同的非负整数列表,并返回列表中不存在的最小非负整数。如果输入有重复项,函数的行为并不重要。这可以在线性时间内实现,只使用列表(没有数组或向量或其他具有有效随机访问的数据结构)?
(这个出现在here上。)
发布于 2011-11-30 21:27:28
如果l包含0和(length l) - 1之间的所有数字,则minout l为length l,否则它位于[0..(length l - 1)]中。所以minout l总是在[0..(length l)]中,只有[0..(length l - 1)]中的l元素是相关的。我们可以丢弃剩余的元素。使用这个想法,我们可以实现线性时间分治解决方案。与合并排序不同,在递归的每一步,我们只递归到两个子列表中的一个,每个子列表的大小最多是原始列表的一半(在做了一些线性工作之后)。这给出了线性时间复杂度。
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时在课堂上遇到它的。
发布于 2011-12-02 04:59:04
Richard Bird在他的书Pearls of Functional Algorithm Design的第一章中描述了这个问题。(这一章恰好是亚马逊上提供的预览。)
https://stackoverflow.com/questions/8326660
复制相似问题