有关数组元素缺失问题 [英] question about missing element in array

问题描述

我已经由麻省理工学院大学继起本书介绍的算法第二版的问题

i have following problem from book introduction algorithm second edition by MIT university

问题是以下

这是数组A [1。 。 n]的包含的所有整数从0到n，除了之一。这将是容易       通过使用一个辅助阵列B〔0，以确定在O（n）的时间丢失的整数。 。 N]       然而，记录哪些数字显示在答：在这个问题上，我们不能访问       在一整个整数跟单操作。 A的元素被重新presented       在二元的，我们可以用它来访问它们唯一的操作就是取第j个位       的[I]，这需要一定的时间。

An array A[1 . . n] contains all the integers from 0 to n except one. It would be easy to determine the missing integer in O(n) time by using an auxiliary array B[0 . . n] to record which numbers appear in A. In this problem, however, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the j th bit of A[i]," which takes constant time.

显示，如果我们只使用这个操作，我们仍然可以决定澳失踪整数（n）的时间

Show that if we use only this operation, we can still determine the missing integer in O(n) time

请帮忙

推荐答案

打电话给你丢失的数量 M 。

Call your missing number M.

您可以拆分您的阵列成两部分取决于 A [1] 的最低显著位是1还是0。这两部分的小（称之为 P_1 ）至多（N-1）的大小/ 2 元素，它会告诉你是否 M 的至少显著位是1还是0。

You can split your array into two parts depending on whether the least significant bit of A[i] is a 1 or a 0. The smaller of the two parts (call it P_1) is at most (n-1)/2 elements in size, and it tells you whether M's least significant bit is a 1 or a 0.

现在考虑 P_1 元素的第2位。再次，这部分可以被一分为二，并在两部分中较小（ P_2 ）告诉你该位是否应该是一个1或0。

Now consider the 2nd bit for the elements of P_1. Again, this part can be split in two, and the smaller of the two parts (P_2) tells you whether this bit should be a 1 or a 0.

执行要去（ P_3 ， P_4 ，...），直到你哪些工作全部位。

Carry on going (P_3, P_4, ...) until you've worked out what all the bits are.

您可以证明这是 O（N），因为你基本上是在看 N + N / 2 + N / 4 + .. 您的阵列中不同的位，这和小于 2N 。

You can prove that this is O(n) because you are essentially looking at n + n/2 + n/4 + ... different individual bits in your array, and this sum is less than 2n.

这篇关于有关数组元素缺失问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！