我同事在面试中提出了一个有趣的问题：
假设你被给予一个未排序的、非常长的无符号64位整数列表。你如何找到列表中不存在的最小的非负整数？
后续问题：既然已经提出了排序的显而易见的解决方案，你能否比O(n log n)更快地完成任务？
后续问题：你的算法必须在计算机上运行，例如1GB的内存。
澄清：这个列表在RAM中，尽管它可能占用大量内存。你预先知道列表的大小N。
在一个列表中找到最小的未出现的整数
91
- PeterAllenWebb
15
6考虑到你谈论的是一个无符号整数，我认为你可以省略掉“非负”的部分，以使表述更加简明。 - KevenDenen
4问题很基础，除非我完全错了，但是正如其他人所提到的，有些需要问的问题或者应该说明的假设。 - James Black
8这是一个例子，其中说“O(n)”并不意味着太多。即使您将2^64位数组存储在复活节岛的黏土片上，并通过鸽子邮递员访问它，该算法仍然是O（n）。 - I. J. Kennedy
6在面试中更改内存要求，这是一个非常好的面试问题。;-) - Chris Ballance
1我认为很有趣的是所有答案都采用了相同的通用解决方案（对数组进行排序并找到打破序列的第一个值），但它们都使用了不同的排序方法（修改版快速排序，基数排序等）。被接受的答案相当于一种计数排序，它会丢弃超过N的元素。 - Joren
显示剩余10条评论
28个回答
1
以下是我用Java编写的答案：
基本思路： 1- 循环遍历数组，丢弃重复的正数、零和负数，同时求出其余数的总和、最大正数，并将唯一的正数存储在Map中。
2- 计算最大值乘以（最大值加1）除以2的总和。
3- 计算步骤1和步骤2计算出的总和之间的差异。
4- 再次循环从1到[总和差异，最大值]的最小值，并返回不在步骤1中填充的Map中的第一个数字。
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;
}
- Rami
1
虽然隐藏因素相当大，但您可以在O(n)时间和O(1)附加空间内完成它。这不是解决问题的实用方法，但仍然可能很有趣。
对于每个无符号64位整数（按升序排列），迭代列表直到找到目标整数或达到列表末尾。如果到达列表末尾，则目标整数是不在列表中的最小整数。如果到达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)。特别要注意的是，即使找到答案后，该函数仍会继续检查目标整数。如果该函数在找到答案后立即返回，则外部循环运行的次数将受到答案大小的限制，而答案大小又受n的限制。这种改变会使运行时间变为O(n^2)，尽管速度会更快。
- Will Harris
1
真的很有趣，一些空间复杂度为O(1)，时间复杂度为O(n)的算法在实践中对这个问题的失败是多么可怕。 - PeterAllenWebb
1
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 !!");
}
}
- ranjeet
1
感谢egon、swilden和Stephen C的启发。首先，我们知道目标值的范围，因为它不能大于列表的大小。此外，一个1GB的列表最多可以包含134217728（128 * 2^20）个64位整数。
哈希部分 我建议使用哈希来显著减少我们的搜索空间。首先，对列表的大小进行平方根运算。对于一个1GB的列表，N=11,586。设置一个大小为N的整数数组。遍历列表，并将找到的每个数字的平方根作为哈希值。在哈希表中，增加该哈希值的计数器。接下来，遍历哈希表。你找到的第一个不等于其最大大小的桶定义了你的新搜索空间。
位图部分 现在设置一个与你的新搜索空间大小相等的常规位图，再次遍历源列表，在你的搜索空间中找到每个数字时填充位图。当你完成时，位图中第一个未设置的位将给出你的答案。
这将在O(n)时间和O(sqrt(n))空间内完成。
哈希部分 我建议使用哈希来显著减少我们的搜索空间。首先，对列表的大小进行平方根运算。对于一个1GB的列表，N=11,586。设置一个大小为N的整数数组。遍历列表，并将找到的每个数字的平方根作为哈希值。在哈希表中，增加该哈希值的计数器。接下来，遍历哈希表。你找到的第一个不等于其最大大小的桶定义了你的新搜索空间。
位图部分 现在设置一个与你的新搜索空间大小相等的常规位图，再次遍历源列表，在你的搜索空间中找到每个数字时填充位图。当你完成时，位图中第一个未设置的位将给出你的答案。
这将在O(n)时间和O(sqrt(n))空间内完成。
（*您可以使用位移等技术来更高效地完成此操作，只需相应地改变桶的数量和大小即可。）
- Nic
2
1我喜欢将搜索空间划分为Root-N个桶以减少内存占用的想法，但列表中的重复项会破坏这种方法。我不知道它是否可以修复。 - PeterAllenWebb
你说得对，我忽略了重复的条目。我不确定是否可以解决这个问题。 - Nic
1
如果在一组数字中只有一个缺失的数字，找到缺失的数字最简单的方法是对该数列求和，然后从总和中减去列表中的每个值。最终的值就是缺失的数字。
- Jeff Lundstrom
2
是的，这是另一个经典的面试问题。 - PeterAllenWebb
1更简单的方法是将列表中的数字进行异或运算，将范围内的数字进行异或运算，然后将结果进行异或运算。 - John Kurlak
0
1) 过滤负数和零
2) 排序/去重
3) 访问数组
复杂度: O(N) 或 O(N * log(N))
使用 Java8
public int solution(int[] A) {
int result = 1;
boolean found = false;
A = Arrays.stream(A).filter(x -> x > 0).sorted().distinct().toArray();
//System.out.println(Arrays.toString(A));
for (int i = 0; i < A.length; i++) {
result = i + 1;
if (result != A[i]) {
found = true;
break;
}
}
if (!found && result == A.length) {
//result is larger than max element in array
result++;
}
return result;
}
- Abdullah Lubbadeh
0
使用Python并不是最高效的方式，但是是正确的。
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import datetime
# write your code in Python 3.6
def solution(A):
MIN = 0
MAX = 1000000
possible_results = range(MIN, MAX)
for i in possible_results:
next_value = (i + 1)
if next_value not in A:
return next_value
return 1
test_case_0 = [2, 2, 2]
test_case_1 = [1, 3, 44, 55, 6, 0, 3, 8]
test_case_2 = [-1, -22]
test_case_3 = [x for x in range(-10000, 10000)]
test_case_4 = [x for x in range(0, 100)] + [x for x in range(102, 200)]
test_case_5 = [4, 5, 6]
print("---")
a = datetime.datetime.now()
print(solution(test_case_0))
print(solution(test_case_1))
print(solution(test_case_2))
print(solution(test_case_3))
print(solution(test_case_4))
print(solution(test_case_5))
- smentek
0
可以使用unordered_set来存储所有正数，然后我们可以从1迭代到unordered_set的长度，并查看第一个不出现的数字。
int firstMissingPositive(vector<int>& nums) {
unordered_set<int> fre;
// storing each positive number in a hash.
for(int i = 0; i < nums.size(); i +=1)
{
if(nums[i] > 0)
fre.insert(nums[i]);
}
int i = 1;
// Iterating from 1 to size of the set and checking
// for the occurrence of 'i'
for(auto it = fre.begin(); it != fre.end(); ++it)
{
if(fre.find(i) == fre.end())
return i;
i +=1;
}
return i;
}
- Mohit Anand
0
def solution(A):
index = 0
target = []
A = [x for x in A if x >=0]
if len(A) ==0:
return 1
maxi = max(A)
if maxi <= len(A):
maxi = len(A)
target = ['X' for x in range(maxi+1)]
for number in A:
target[number]= number
count = 1
while count < maxi+1:
if target[count] == 'X':
return count
count +=1
return target[count-1] + 1
以上解决方案获得了100%的分数。
- Angelo
0
这里有一个Java答案，它不修改输入，并使用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);
}
- Dave L.
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接