找出最小的整数不在列表 [英] Find the Smallest Integer Not in a List

问题描述

这是有趣的面试问题是我的一个同事使用：

An interesting interview question that a colleague of mine uses:

假设你被赋予了64位无符号整数一个很长的，未分类的列表。你会如何​​找到最小的非负整数，它的不的出现在列表中？

Suppose that you are given a very long, unsorted list of unsigned 64-bit integers. How would you find the smallest non-negative integer that does not occur in the list?

追问：？现在，通过排序显而易见的解决方案已经提出，可你比为O（n log n）的

FOLLOW-UP: Now that the obvious solution by sorting has been proposed, can you do it faster than O(n log n)?

追问：你的算法到计算机，比如上运行，1GB的内存

FOLLOW-UP: Your algorithm has to run on a computer with, say, 1GB of memory

澄清：该列表是在RAM中，尽管它可能消耗大量的它。你给出列表的大小，比如说N，提前

CLARIFICATION: The list is in RAM, though it might consume a large amount of it. You are given the size of the list, say N, in advance.

推荐答案

如果该数据结构可以被突变的地方，并支持随机访问，那么你可以做到这一点在O（n）时间及O（1）额外的空间。只需通过阵列顺序和各指标写入该指数由值指定的，递归放置任何值在那个位置，它的位置和扔掉价值指数的价值> N.然后再次通过数组寻找现货这是最小的值不是数组中 - 在这里值不匹配索引。这导致至多3N比较，并只使用几个值价值的临时空间。

If the datastructure can be mutated in place and supports random access then you can do it in O(N) time and O(1) additional space. Just go through the array sequentially and for every index write the value at the index to the index specified by value, recursively placing any value at that location to its place and throwing away values > N. Then go again through the array looking for the spot where value doesn't match the index - that's the smallest value not in the array. This results in at most 3N comparisons and only uses a few values worth of temporary space.

# 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

这篇关于找出最小的整数不在列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！