arrays - 找到不在列表中的最小整数

Question

我的一位同事使用的一个有趣的面试问题:

假设给你一个很长的、未排序的无符号 64 位整数列表。您如何找到没有出现在列表中的最小非负整数？

跟进:既然已经提出了明显的排序解决方案，你能做到比 O(n log n) 更快吗？

跟进:您的算法必须在具有 1GB 内存的计算机上运行

澄清:该列表在 RAM 中，尽管它可能会占用大量内存。预先给定列表的大小，比如 N。

Answer 1

如果数据结构可以就地变异并支持随机访问，那么您可以在 O(N) 时间和 O(1) 额外空间内完成。只需按顺序遍历数组，对于每个索引，将索引处的值写入 value 指定的索引，递归地将该位置的任何值放到它的位置，并丢弃值 > 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