首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在线性时间内找到列表中不存在的最小非负整数,仅使用列表

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

Stack Overflow用户
提问于 2011-11-30 21:25:13
回答 2查看 945关注 0票数 5

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

(这个出现在here上。)

EN

回答 2

Stack Overflow用户

回答已采纳

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

代码语言:javascript
复制
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时在课堂上遇到它的。

票数 12
EN

Stack Overflow用户

发布于 2011-12-02 04:59:04

Richard Bird在他的书Pearls of Functional Algorithm Design的第一章中描述了这个问题。(这一章恰好是亚马逊上提供的预览。)

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/8326660

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档