减少运行时为O（n） [英] Decrease runTime to O(n)

问题描述

我得到这个问题的硬件，我无法弄清楚如何做到这一点：
数组A [1 ... N]包含了所有的整数从0到n，除了之一。该数组是没有排序。
在这个问题上，我们不能访问整个整数A和一个单一的操作。
A的元素是psented二进制重新$ P $，我们可以用它来访问它们唯一的操作就是取的[I]第j个位，这需要一定的时间。

I got this question for HW and I can't figure out how to do it:
An array A[1...n] contains all the integers from 0 to n except one. The array is not sorted.
In this problem, 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 jth bit of A[i]", which takes constant time.

我要找到在O（n）时间丢失的整数。

I have to find the missing integer in O(n) time.

它需要mormally做到这一点的时间是O（NlgN） （N个阵列上运行，并获取所有这些都是N个功能位 - LGN位）。

The time it takes to do it mormally is O(NlgN) (run on the N array, and fetch all the bits which are function of N - lgn bits).

如何能做到不读所有的位？

How can I do it without reading all the bits?

推荐答案

让我们现在假设n为2 ^ K - 1对某个k

Let's assume for now that n is 2^k - 1 for some k.

让我们再来看一个例子，其中k = 3。

Let's also look at an example where k = 3.

000
001
010
011
100
101
110
111

您会发现，当有全套，像上面显示的，每列（每个数字的地方）具有一和零相同的号码。当然，为方便起见，我们显示这是排序，但在现实中，我不应该说它是。

You'll notice that when there is a full set, like the one shown above, each column (each digit's place) has the same number of ones and zeros. Of course, for convenience we are showing this as sorted, but in reality, I am not stating that it is.

让我们来看看下面的列表

Let's take a look at the following list

000
001
010
011
100
110
111

我们看所有的元素（为O（n））的第一位，并找出哪些计数小于其他。

We look at the first bit of all of the elements ( O(n) ) and figure out which count is less than the other.

我们看到，对于第一比特，有一个数字与1中的最显著位缺失。这意味着，我们知道我们的号码有一个在其最显著位。

We see that for the first bit, there is a number with the 1 in the most significant bit missing. This means that we know that our number has a one in its most significant bit.

基本上，我们划分成两个集合，之一，最显著位是1和一个其中最显著位为0越小集我们展示了位缺失的数目也有

Basically, we partition into two sets, one where the most significant bit is 1 and one where the most significant bit is 0. The smaller set shows us what bit the missing number has.

我们做的更小的分区一样的东西。

We do the same thing on the smaller partition.

由于它是O（n）+ O（N / 2）+ O（N / 4）...它基本上是O（2N），这是O（n）。

Since it is O(n) + O(n/2) + O (n/4) ... it is basically O (2n) which is O (n).

修改

有关的一般情况下，参阅下面的文档，底部第1页。

For the general case, refer to the following document, bottom of page 1.

基本上，它涉及利用的事实，即当n不为二的幂，则可以考虑到给定的n，你知道究竟有多少应属于下位= 1分区和位的事实= 0分区，如果这是一个完整的一套。

Basically, it involves making use of the fact that when n is not a power of two, you can take into account the fact that given n, you know exactly how many should fall under the bit=1 partition and the bit=0 partition if this was a complete set.

这篇关于减少运行时为O（n）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！