Haskell：在线性时间内找到列表中最小的非负整数，仅使用列表 [英] Haskell : find smallest nonnegative integer not in list in linear time, using only lists

问题描述

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

（This came up 这里）

解决方案

如果 l 具有 0 和（长度l） - 1 之间的所有数字。包括在内，那么 minout l 是长度l ，否则它位于 [0 .. （长度1 - 1）] 。因此 minout l 总是位于 [0 ..（length l）] 中，并且只有 l 是 [0 ..（length l - 1）] 是相关的。我们可以放弃其余的元素。使用这个想法，我们可以实现一个线性时间的分而治之的解决方案。与合并排序不同的是，在递归的每一步中，我们只会将一个递归到两个子列表中，每个子列表最多只有原始大小的一半（在完成一些线性工作之后）。这给出了一个线性的时间复杂度。

  minout :: [Int]  - > Int 
 minout = minoutaux 0 
其中
 minoutaux :: Int  - > [Int]  - > Int  -  \list base  - >最小的整数> =在列表中没有发生基数
 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 + n 2≤x，x < base + n] 
  

在上面的代码中， minoutaux 是一个给定基本整数和具有不同条目的列表的函数，返回至少为基数并且不出现在列表中的最小整数。正如前面所解释的那样，它放弃了可以丢弃的不相关的元素，并生成两个列表，包括位于[ base ， base + n2 ）（称为 smallpart ）和[ base + n2 ， base + n ）（称为 bigpart ）。每个这些列表的长度最多为 n2 。如果长度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时在课堂上遇到了它。

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)?

(This came up here.)

解决方案

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]

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.

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)

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.

This question and solution is not my original; I came across it in class when I learnt Haskell.

这篇关于Haskell：在线性时间内找到列表中最小的非负整数，仅使用列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！