我在麻省理工大学的《算法介绍第二版》一书中遇到以下问题
问题如下
数组 A[1 。 。 n] 包含 0 到 n 之间除 1 之外的所有整数。这很容易
使用辅助数组 B[0 来在 O(n) 时间内确定丢失的整数。 。 ]
记录 A 中出现了哪些数字。但是，在这个问题中，我们无法访问
通过一次操作即可得到 A 中的整个整数。 A的元素表示为
在二进制中，我们可以用来访问它们的唯一操作是“获取第 j 位
A[i]”，这需要常数时间。
证明如果我们只使用这个操作，我们仍然可以在 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.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
