假设我有整数[0, 1, 2, 4, 6]的连续范围,其中3是第一个“丢失”的数字。我需要一个算法来找到第一个“洞”。由于范围非常大(可能包含2^32条目),因此效率很重要。数字的范围存储在磁盘上;空间效率也是一个主要问题。
最佳的时空高效算法是什么?

最佳答案

使用二进制搜索。如果一个数字区域没有洞,那么该区域的结束和开始之间的差异也将是该区域中的条目数。
因此,您可以从整个数字列表开始,并根据上半部分是否有间隙来切掉上半部分或下半部分。最终你会到达一个有两个入口的区域,中间有一个洞。
时间复杂度为O(log N)。与线性扫描相比,其最坏情况是O(N)

关于algorithm - 在排序列表中找到第一个“缺失”数字,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/11385896/

10-11 23:03
查看更多