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

一个有趣的采访问题，我的一个同事使用：

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

后续：现在已经提出了sorting的明显解决scheme，你能比O（n log n）更快吗？

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

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

Answer 1

如果数据结构可以在适当位置进行变异并支持随机访问，那么可以在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 

Answer 2

这是一个简单的使用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布尔值数组”可能被编码为一个“位图”或“位集”，表示为一个byte或int数组。 这通常使用较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需要首先通过列表来确定Xmax和Xmin 。
• 因此最小的最坏情况空间要求是ceiling(log2(N)) * (Xmax - Xmin)位。

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

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

---

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

Answer 3

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

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

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

Answer 4

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

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

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

这节省了大量的计算。

Answer 5

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

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

Answer 6

为了说明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" 

Answer 7

对于空间有效的方法，所有的值都是不同的，你可以在空间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) 。

Answer 8

我只是对它们进行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") 

Answer 9

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

Answer 10

你可以在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），即使它会快得多。

Answer 11

感谢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））空间完成。

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

Answer 12

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

Answer 13

  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 !!"); } } 

Answer 14

我们可以使用一个哈希表来保存这些数字。 一旦完成所有的数字，从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) 。

Answer 15

这是我用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; } 

Answer 16

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

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

Answer 17

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

 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）

Answer 18

我不确定是否有这个问题。 但是，如果对于列表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）个连续整数减去丢失的数字之和。

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

Answer 19

做得好的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只是对读者的一个练习。 🙂

Answer 20

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这一点留给了解更好的工具的人。

Answer 21

下面是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); }