找出不在列表中的最小整数 [英] 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) 额外空间内完成.只需按顺序遍历数组，对于每个索引，将索引处的值写入 value 指定的索引，递归地将该位置的任何值放置到其位置并丢弃值 > N.然后再次遍历数组寻找该位置其中 value 与索引不匹配 - 这是不在数组中的最小值.这导致最多 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屋！