我有麻省理工大学的书籍介绍算法第二版的问题
问题是如下
数组A [1..n]包含从0到n的所有整数,除了一个.通过使用辅助数组B [0,很容易在O(n)时间内确定丢失的整数..n]记录哪些数字出现在A.然而,在这个问题中,我们无法通过单个操作访问A中的整个整数.A的元素以二进制表示,我们可以用来访问它们的唯一操作是"获取A [i]的第j位",这需要恒定的时间.
表明如果我们只使用这个操作,我们仍然可以在O(n)时间内确定缺失的整数
请帮忙
拨打您丢失的号码M.
您可以将数组拆分为两部分,具体取决于最低有效位A[i]是1还是0.两部分中的较小部分(称之为P_1)最多是(n-1)/2元素大小,它会告诉您是否M是最不重要的位是1还是0.
现在考虑第二位的元素P_1.同样,这部分可以分为两部分,两部分中较小的一部分(P_2)告诉你这个位是1还是0.
继续前进(P_3,P_4......),直到你弄清楚所有的位是什么.
您可以证明这是O(n)因为您实际上是n + n/2 + n/4 + ...在查看数组中的不同单个位,并且此总和小于2n.