仅使用列表查找线性时间不在列表中的最小非负整数 [英] Find smallest nonnegative integer not in list in linear time, using only lists
问题描述
考虑一个函数minout :: [Int] -> Int，该函数获取一个不同的非负整数列表，并返回列表中不存在的最小非负整数.如果输入重复，则函数的行为无关紧要.是否可以仅使用列表(不使用数组或向量或具有有效随机访问功能的其他数据结构)在线性时间内实现?
Consider a function minout :: [Int] -> Int which takes a list of distinct nonnegative integers, and returns the smallest nonnegative integer not present in the list. The behaviour of the function if the input has duplicates does not matter. Can this be implemented in linear time, using only lists (no arrays or vectors or other data structures with efficient random access)?
(这出现在此处.)
推荐答案
如果l具有在0和(length l) - 1之间的所有数字，则minout l是length l，否则，它位于minout l始终位于[0..(length l)]中，并且仅[0..(length l - 1)]中的l元素是相关的.我们可以丢弃其余的元素.使用这个想法，我们可以实现线性时间分而治之的解决方案.与合并排序不同，在递归的每个步骤中，我们仅递归到两个子列表中的一个，每个子列表的大小最多为原始大小的一半(在执行一些线性工作之后).这给出了线性的时间复杂度.
If l has all numbers between 0 and (length l) - 1 inclusive, then minout l is length l, otherwise, it lies in [0..(length l - 1)]. So minout l always lies in [0..(length l)], and only the elements of l which are in [0..(length l - 1)] are relevant. We can discard the remaining elements. Using this idea we can implement a linear-time divide-and-conquer solution. Unlike in merge sort, at each step of the recursion, we recurse into only one of two sublists each of which is at most half the size of the original (after doing some linear work). This gives a linear time complexity.
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.
In the above code, minoutaux is a function which given a "base" integer and a list with distinct entries, returns the smallest integer which is at least base and does not occur in the list. To do this, it discards the "irrelevant" elements which can be discarded, as explained earlier, and generates two lists, consisting of those numbers which lie in [base, base + n2) (called smallpart), and [base + n2, base + n) (called bigpart). Each of these lists will have length at most n2. If length smallpart == n2, then smallpart has all numbers in [base, base + n2), and so the answer must lie in bigpart, otherwise, there is a "gap" in smallpart itself, so the answer lies in smallpart.
为什么它要线性运行?首先，说遍遍整个长度为N的列表几次，这需要进行10N次操作.然后，在较小的列表上调用minoutaux，列表的大小最大为N/2.因此，我们最多还有10N/2个操作.然后是10N/4、10N/8，依此类推.加上所有这些，我们得到10(2N)= 20N的边界. (常数10仅作为示例)
Why does this run in linear time? First, the whole list of length N is traversed a few times, which needs some 10N operations, let's say. Then minoutaux is called on a smaller list, of size at most N/2. So we have (at most) 10N/2 more operations. Then 10N/4, 10N/8, and so on. Adding all these, we get a bound of 10(2N) = 20N. (the constant 10 was just used as an example)
在这里，我们多次遍历列表以计算其长度，计算smallpart，计算bigpart，依此类推.通过一次完成所有这些操作，就可以相当轻松地优化它.但是，这仍然是线性时间解决方案，我想使代码更清晰，而不是在恒定因子上进行优化.
Here we are traversing the list multiple times to compute its length, compute smallpart, compute bigpart, and so on. One could optimize that fairly easily by doing all this in a single pass. However this is still a linear time solution, and I wanted to make the code clearer, rather than optimize on constant factors.
这个问题和解决方案不是我的原创；当我学习Haskell时，我在课堂上遇到了它.
This question and solution is not my original; I came across it in class when I learnt Haskell.
这篇关于仅使用列表查找线性时间不在列表中的最小非负整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
