在包含最多40亿个整数的未排序数组中找到缺失的32位整数

Question

在包含最多40亿个整数的未排序数组中找到缺失的32位整数

pie*_*fou 6 algorithm binary-search programming-pearls

这是描述的问题Programming pearls.我无法理解作者所描述的二进制搜索方法.任何人都可以帮忙详细说明吗？谢谢.

编辑:我一般可以理解二进制搜索.我只是无法理解如何在这种特殊情况下应用二进制搜索.如何确定缺失的数字是否在某个范围内,以便我们可以选择另一个.英语不是我的母语,这是我无法理解作者的一个原因.所以,请使用普通英语:)

编辑:谢谢大家的好评和评论!我从解决这个问题中学到的最重要的一课就是二元搜索不仅适用于排序数组!

Answer 1

Ron*_*erg 9

本网站上有更多信息.引自那里:

"根据表示每个整数的20位来查看这个二进制搜索是有帮助的.在算法的第一遍中,我们读取(最多)一百万个输入整数,并将那些带有前导零位的数据写入一个磁带,这两个磁带中有一个包含最多500,000个整数,因此我们接下来将该磁带用作当前输入并重复探测过程,但这次是在第二个磁带上.如果是原始输入磁带包含N个元素,第一遍将读取N个整数,第二次传递最多为N/2,第三次传递最多为N/4,依此类推,因此总运行时间与N成正比.可以找到缺失的整数通过在磁带上排序然后扫描,但这需要与N log N成比例的时间."

正如您所看到的,这是二元搜索算法的一种变体:将问题分成两部分并解决其中一个较小部分的问题.

在我们完成一次完整数据传递的那一刻,复杂性就是O(n),所以O(log(n))就出来了.现在O(n)意味着存在一些常数c,使得算法的运行时间由上面的c*n限制,因此O(2n)与O(n)完全相同.rwwilden,你的错误只是计算传球,传球的价值也翻倍. (7认同)
事实并非如此.复杂性实际上是O(log n).假设问题空间为8(所以我们需要找到0,1,2,3,4,5,6,7范围内缺失的整数).这最多需要3遍算法.如果我们将问题空间加倍到16,我们最多需要4次算法通过.因此,尽管问题空间从8增加到16,但解决问题所需的时间仅增加了1.33333 ...如果我们再次加倍,解决问题所需的时间仅增加1.25倍.这意味着算法的复杂性不是线性的(因此不是O(2n)). (2认同)

归档时间：	16 年，3 月前
查看次数：	4945 次
最近记录：	15 年，9 月前