查找不在列表中的最小整数
我的一位同事使用的一个有趣的访谈问题：
假设您得到了一个很长的，未排序的无符号64位整数列表。您将如何找到列表中未出现的最小非负整数？
跟进：现在已经提出了明显的排序解决方案，您可以比O（n log n）更快吗？
跟进：您的算法必须在具有1GB内存的计算机上运行
澄清：该列表位于RAM中，尽管它可能会消耗大量的内存。预先给您列表的大小，例如N。 问题来源于stack overflow
写回答
-
如果数据结构可以在适当位置进行突变并支持随机访问，则可以在O（N）时间和O（1）额外空间中进行操作。只需依次遍历数组，并为每个索引将索引处的值写入由value指定的索引，然后将该位置处的任何值递归地放置到该位置，并丢弃值>N。然后再次遍历该数组以查找该点其中value与索引不匹配-这是不在数组中的最小值。这样最多可以进行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
2020-02-08 14:04:00赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
