问题描述
比方说，我有一个整数的连续范围 [0，1，2，4，6] ，其中 3 是第一个失踪数。我需要一个算法来找出这首洞。由于范围是非常大的（含或许 2 ^ 32 项），效率是很重要的。数的范围被存储在磁盘上;空间效率也是一个主要关注点。
Let's say I have the continuous range of integers [0, 1, 2, 4, 6], in which the 3 is the first "missing" number. I need an algorithm to find this first "hole". Since the range is very large (containing perhaps 2^32 entries), efficiency is important. The range of numbers is stored on disk; space efficiency is also a main concern.
什么是最好的时间和空间效率的算法？
What's the best time and space efficient algorithm?
推荐答案
使用二进制搜索。如果一个数字范围没有孔，则该范围的端部和开始之间的差异也将在范围中的条目数。
Use binary search. If a range of numbers has no hole, then the difference between the end and start of the range will also be the number of entries in the range.
因此，可以以数字开头的完整列表，并砍掉或者基于今年上半年是否有缝隙的第一或第二的一半。最终，你会来到一个范围内的两个条目，在中间有一个洞。
You can therefore begin with the entire list of numbers, and chop off either the first or second half based on whether the first half has a gap. Eventually you will come to a range with two entries with a hole in the middle.
这样做的时间复杂度为 O（日志N）。对比线性扫描，其最坏的情况是 O（N）。
The time complexity of this is O(log N). Contrast to a linear scan, whose worst case is O(N).
这篇关于找到第一个＆QUOT;失踪＆QUOT;在排序列表数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！