查找不在列表中的最小整数

一个有趣的采访问题,我的一个同事使用:

假设给出了一个非常长,未sorting的无符号64位整数列表。 你会如何find不在列表中出现的最小的非负整数?

后续:现在已经提出了sorting的明显解决scheme,你能比O(n log n)更快吗?

后续操作:你的algorithm必须在有1GB内存的计算机上运行

澄清:列表在RAM中,虽然它可能会消耗大量的内存。 你预先给N的名单的大小。

如果数据结构可以在适当位置进行变异并支持随机访问,那么可以在O(N)时间和O(1)额外空间中进行。 只需按顺序遍历数组,并对每个索引将索引处的值写入由value指定的索引处,recursion地将该位置处的任何值放在其位置并将值丢弃> N。然后再次通过数组查找该位置其中值与索引不匹配 – 这是数组中最小的值。 这导致最多3N的比较,只使用一些价值的临时空间。

# Pass 1, move every value to the position of its value for cursor in range(N): target = array[cursor] while target < N and target != array[target]: new_target = array[target] array[target] = target target = new_target # Pass 2, find first location where the index doesn't match the value for cursor in range(N): if array[cursor] != cursor: return cursor return N 

这是一个简单的使用O(N)空间的O(N)解决scheme。 我假设我们将input列表限制为非负数,并且我们希望find不在列表中的第一个非负数。

  1. find列表的长度; 可以说这是N
  2. 分配一组N布尔值,初始化为全部为false
  3. 对于列表中的每个数字X ,如果X小于N ,则将数组的第X'th元素设置为true
  4. 从索引0开始扫描数组,查找第一个为false元素。 如果你在索引Ifind第一个false ,那么I就是答案。 否则(即当所有元素都是true )答案是N

实际上,“ N布尔值数组”可能被编码为一个“位图”或“位集”,表示为一个byteint数组。 这通常使用较less的空间(取决于编程语言),并允许第一次false的扫描更快。


这就是algorithm的工作原理。

假设列表中的N数字不明显,或者其中一个或多个大于N 这意味着必须至less有一个不在列表中的数字0 .. N - 1 。 因此find最小缺失数的问题必须减less到寻找最小缺失数小于N 。 这意味着我们不需要跟踪大于或等于N的数字,因为它们不会是答案。

前一段的替代scheme是该列表是从0 .. N - 1的数字的排列。 在这种情况下,第3步将数组的所有元素设置为true ,第4步告诉我们第一个“缺less”数字是N


该algorithm的计算复杂度为O(N) ,具有相对较小的比例常数。 它会在列表中进行两次线性传递,如果已知列表长度,则只传递一次。 不需要在内存中表示整个列表,所以algorithm的渐进式内存使用正是表示布尔数组所需要的; 即O(N)位。

(相比之下,依赖于内存中sorting或分区的algorithm假设您可以在内存中表示整个列表,以问题的forms提出问题,这将需要O(N)个64位字)。


@Jorn评论说,步骤1到3是计数sorting的变体。 从某种意义上说,他是对的,但差异是显着的:

  • 计数sorting需要一个(至less) Xmax - Xmin计数器数组,其中Xmax是列表中最大的数字, Xmin是列表中的最小数字。 每个计数器必须能够代表N个状态; 即假定二进制表示,它必须具有整数types(至less) ceiling(log2(N))位。
  • 为了确定数组大小,计数sorting需要首先通过列表来确定XmaxXmin
  • 因此最小的最坏情况空间要求是ceiling(log2(N)) * (Xmax - Xmin)位。

相比之下,上述algorithm在最差和最好的情况下只需要N位。

然而,这种分析导致了这样的直觉:如果algorithm首先通过列表寻找零(并且如果需要的话统计列表元素),如果find零,则它将更快地得到没有空间的答案。 如果在列表中find至less一个零的概率很高,那么这样做绝对值得。 而这个额外的传球并没有改变整体的复杂性。


编辑:我已经改变了algorithm的描述使用“数组布尔”,因为人们显然发现我的原始描述使用位和位图混淆。

由于OP现在已经规定原来的列表是在RAM中保存的,并且计算机只有1GB的内存,所以我打算一下子出来,预测答案是零。

1GB的RAM意味着列表中最多可以有134,217,728个数字。 但有2 64 = 18,446,744,073,709,551,616可能的数字。 所以列表中零的概率是137,438,953,472中的1。

相比之下, 今年我遭雷击的几率是七十万分之一。 而我被陨石击中的几率约为10万亿分之一。 所以,由于天体不幸死亡,我的科学杂志写在科学杂志上的可能性大约是十倍,而答案不是零。

正如其他答案中指出的那样,您可以进行sorting,然后直接扫描,直到find空白。

您可以将algorithm复杂度提高到O(N),并通过使用修改的QuickSort保留O(N)空间,从而消除不包含空位的潜在候选项的分区。

  • 在第一个分区阶段,删除重复项。
  • 分区完成后,查看下部分区中的项目数量
  • 这个值是否等于用于创build分区的值?
    • 如果是的话,这意味着差距在更高的分区。
      • 继续快速sorting,忽略较低的分区
    • 否则,差距是在较低的分区
      • 继续快速sorting,忽略较高的分区

这节省了大量的计算。

由于数字长度都是64位,所以我们可以使用基数sorting ,即O(n)。 sorting他们,然后扫描他们,直到你find你要找的东西。

如果最小的数字是零,则向前扫描,直到find间隙。 如果最小的数字不是零,答案是零。

为了说明O(N)思维的一个缺陷,这里是一个使用O(1)空间的O(N)algorithm。

 for i in [0..2^64): if i not in list: return i print "no 64-bit integers are missing" 

对于空间有效的方法,所有的值都是不同的,你可以在空间O( k )和时间O( k*log(N)*N )做到这一点。 这是节省空间,没有数据移动,所有操作都是基本的(加上减法)。

  1. U = N; L=0 U = N; L=0
  2. 首先分割k区域中的数字空间。 喜欢这个:
    • 0->(1/k)*(UL) + L 0->(2/k)*(UL) + L 0->(3/k)*(UL) + L 0->(UL) + L
  3. 查找每个区域有多less个数( count{i} )。 ( N*k步)
  4. find未满的第一个区域( h )。 这意味着count{h} < upper_limit{h} 。 ( k步)
  5. 如果h - count{h-1} = 1你已经得到了你的答案
  6. 设置U = count{h}; L = count{h-1} U = count{h}; L = count{h-1}
  7. 转到2

这可以通过使用哈希来改进(感谢Nic的这个想法)。

  1. 相同
  2. 首先分割k区域中的数字空间。 喜欢这个:
    • L +(i / k)→L +(i + 1 / k)*(UL)'
  3. inc count{j}使用j = (number - L)/k (if L < number < U)
  4. find第一个没有k个元素的区域( h
  5. 如果count{h} = 1 h是你的答案
  6. 设置U = maximum value in region h L = minimum value in region h

这将运行在O(log(N)*N)

我只是对它们进行sorting,然后遍历序列,直到find一个缺口(包括零和第一个数字之间的差距)。

就algorithm而言,像这样的事情可以做到这一点:

 def smallest_not_in_list(list): sort(list) if list[0] != 0: return 0 for i = 1 to list.last: if list[i] != list[i-1] + 1: return list[i-1] + 1 if list[list.last] == 2^64 - 1: assert ("No gaps") return list[list.last] + 1 

当然,如果你的内存比CPU的更多,你可以创build一个所有可能的64位值的位掩码,并且为列表中的每个数字设置位。 然后查找该位掩码中的第一个0位。 就时间而言,它变成了一个O(n)操作,但在内存要求方面非常昂贵:-)

我怀疑你可以改进O(n),因为我不能看到这样做的方式,不涉及每个数字至less一次。

那个algorithm将会是:

 def smallest_not_in_list(list): bitmask = mask_make(2^64) // might take a while :-) mask_clear_all (bitmask) for i = 1 to list.last: mask_set (bitmask, list[i]) for i = 0 to 2^64 - 1: if mask_is_clear (bitmask, i): return i assert ("No gaps") 

对列表进行sorting,查看第一个和第二个元素,并开始向上,直到出现间隙。

你可以在O(n)时间和O(1)额外的空间内完成,尽pipe隐藏的因素非常大。 这不是一个解决问题的实际方法,但它可能是有趣的。

对于每个无符号的64位整数(按升序)遍历列表,直到find目标整数或者到达列表的末尾。 如果到达列表的末尾,则目标整数是不在列表中的最小整数。 如果达到64位整数的末尾,则每个64位整数都在列表中。

这里是一个Python函数:

 def smallest_missing_uint64(source_list): the_answer = None target = 0L while target < 2L**64: target_found = False for item in source_list: if item == target: target_found = True if not target_found and the_answer is None: the_answer = target target += 1L return the_answer 

这个函数故意低效地保持O(n)。 特别要注意的是,即使在find答案之后,函数仍然检查目标整数。 如果函数一旦find答案就返回,那么外层循环运行的次数将受到被n限制的答案的大小的约束。 这个改变会使运行时间O(n ^ 2),即使它会快得多。

感谢egon,swilden和Stephen C的灵感。 首先,我们知道目标值的界限,因为它不能大于列表的大小。 此外,1GB列表最多可以包含134217728(128 * 2 ^ 20)个64位整数。

散列部分
我build议使用哈希大大减less我们的search空间。 首先,平方根大小的列表。 对于1GB的列表,这是N = 11,586。 设置一个大小为N的整型数组。迭代整个列表,并将每个数字的平方根*作为哈希值。 在你的散列表中,递增该散列的计数器。 接下来,遍历你的哈希表。 你发现的第一个桶不等于它的最大尺寸定义你的新search空间。

位图部分
现在设置一个与新search空间大小相同的常规位图,并再次遍历源列表,在search空间中查找每个数字时填充位图。 完成后,位图中的第一个未定位将会给出答案。

这将在O(n)时间和O(sqrt(n))空间完成。

(*您可以使用类似位移的方式来更有效地执行此操作,并相应地改变桶的数量和大小。)

那么,如果在数字列表中只有一个缺失的数字,find缺失数字的最简单方法是对数列求和,然后减去列表中的每个数值。 最终值是缺less的数字。

  int i = 0; while ( i < Array.Length) { if (Array[i] == i + 1) { i++; } if (i < Array.Length) { if (Array[i] <= Array.Length) {//SWap int temp = Array[i]; int AnoTemp = Array[temp - 1]; Array[temp - 1] = temp; Array[i] = AnoTemp; } else i++; } } for (int j = 0; j < Array.Length; j++) { if (Array[j] > Array.Length) { Console.WriteLine(j + 1); j = Array.Length; } else if (j == Array.Length - 1) Console.WriteLine("Not Found !!"); } } 

我们可以使用一个哈希表来保存这些数字。 一旦完成所有的数字,从0运行一个计数器,直到我们发现最低。 一个相当不错的散列会在一段时间内散列和存储,并在一段时间内检索。

 for every i in X // One scan Θ(1) hashtable.put(i, i); // O(1) low = 0; while (hashtable.get(i) <> null) // at most n+1 times low++; print low; 

如果数组中有n元素,并且是{0, 1, ... n-1} ,那么最坏的情况是,在这种情况下,答案将在n获得,仍然保持为O(n)

这是我用Java编写的答案:

基本思路:1-通过arrays循环抛出重复的正数,零和负数,其余的总和,获得最大的正数,并保持唯一的正数在一个地图。

2-计算总和为max *(max + 1)/ 2。

3-找出步骤1和2中计算的总和之间的差异

4-再次从1循环到[sum difference,max]的最小值,并返回第一步中填入的第一个不在地图中的数字。

 public static int solution(int[] A) { if (A == null || A.length == 0) { throw new IllegalArgumentException(); } int sum = 0; Map<Integer, Boolean> uniqueNumbers = new HashMap<Integer, Boolean>(); int max = A[0]; for (int i = 0; i < A.length; i++) { if(A[i] < 0) { continue; } if(uniqueNumbers.get(A[i]) != null) { continue; } if (A[i] > max) { max = A[i]; } uniqueNumbers.put(A[i], true); sum += A[i]; } int completeSum = (max * (max + 1)) / 2; for(int j = 1; j <= Math.min((completeSum - sum), max); j++) { if(uniqueNumbers.get(j) == null) { //O(1) return j; } } //All negative case if(uniqueNumbers.isEmpty()) { return 1; } return 0; } 

正如Stephen C聪明地指出的那样,答案必须是一个小于数组长度的数字。 然后我会通过二分查找find答案。 这样可以优化最糟糕的情况(所以面试官不能抓住你的假设)。 在一次采访中,请指出你正在这样做,以便在最坏的情况下进行优化。

使用二分查找的方法是从数组的每个元素中减去要查找的数字,然后检查否定结果。

我喜欢“猜测零”的评价。 如果数字是随机的,那么很可能是零。 如果“审查员”设置了一个非随机列表,然后再添加一个,然后再猜测:

 LowNum=0 i=0 do forever { if i == N then leave /* Processed entire array */ if array[i] == LowNum { LowNum++ i=0 } else { i++ } } display LowNum 

最坏的情况是n * N,n = N,但实际上n很可能是一个小数字(例如1)

我不确定是否有这个问题。 但是,如果对于列表1,2,3,5,6和缺less的数字是4,那么可以在O(n)中通过(n + 2)(n + 1)/ 2-(n + 1)N / 2

编辑:对不起,我想我昨天晚上想得太快了。 无论如何,第二部分实际上应该被sum(list)所替代,这就是O(n)来的地方。 公式揭示了它背后的思想:对于n个连续的整数,和应该是(n + 1)* n / 2。 如果有一个缺失的数字,总和将等于(n + 1)个连续整数减去丢失的数字之和。

感谢您指出我正在考虑一些中间件。

做得好的antAasma! 我考虑了大约15分钟的答案,并且以相似的思路向你们提出了一个独立的答案:

 #define SWAP(x,y) { numerictype_t tmp = x; x = y; y = tmp; } int minNonNegativeNotInArr (numerictype_t * a, size_t n) { int m = n; for (int i = 0; i < m;) { if (a[i] >= m || a[i] < i || a[i] == a[a[i]]) { m--; SWAP (a[i], a[m]); continue; } if (a[i] > i) { SWAP (a[i], a[a[i]]); continue; } i++; } return m; } 

m代表“当前最大可能输出给我所知道的第一个我input,并假设没有任何其他的值,直到进入m-1”。

只有当(a [i],…,a [m-1])是值(i,…,m-1)的排列时,才会返回m的这个值。 因此,如果a [i]> = m或者a [i] <i或者a [i] == a [a [i]我们知道m是错误的输出,并且必须至less有一个元素低一些。 所以递减m和交换a [m]我们可以recursion。

如果这不是真的,但是我知道一个[i]!= a [a [i]]我们知道用[a [i]]交换一个[i]会增加元素的数量在自己的地方。

否则,[i]必须等于i,在这种情况下,我们可以增加i,知道达到并包括这个指数的所有值都等于它们的指数。

这个不能进入无限循环的certificate只是对读者的一个练习。 🙂

ant的答案Dafny片段显示为什么就地algorithm可能会失败。 requires前置条件描述了每个项目的值不能超出数组的范围。

 method AntsAasma(A: array<int>) returns (M: int) requires A != null && forall N :: 0 <= N < A.Length ==> 0 <= A[N] < A.Length; modifies A; { // Pass 1, move every value to the position of its value var N := A.Length; var cursor := 0; while (cursor < N) { var target := A[cursor]; while (0 <= target < N && target != A[target]) { var new_target := A[target]; A[target] := target; target := new_target; } cursor := cursor + 1; } // Pass 2, find first location where the index doesn't match the value cursor := 0; while (cursor < N) { if (A[cursor] != cursor) { return cursor; } cursor := cursor + 1; } return N; } 

将代码粘贴到validation程序中,使用和不使用forall ...子句来查看validation错误。 第二个错误是validation者无法为Pass 1循环build立终止条件的结果。 certificate这一点留给了解更好的工具的人。

下面是Java中的一个答案,它不修改input,并使用O(N)时间和N位加上一个小的内存常量开销(其中N是列表的大小):

 int smallestMissingValue(List<Integer> values) { BitSet bitset = new BitSet(values.size() + 1); for (int i : values) { if (i >= 0 && i <= values.size()) { bitset.set(i); } } return bitset.nextClearBit(0); }