找到第一个＆QUOT;失踪＆QUOT;在排序列表数量 [英] Find the first "missing" number in a sorted list

问题描述

比方说，我有一个整数的连续范围 [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;在排序列表数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！