2

一个数组a[]包含从 0 到 N 的所有整数，除了一个。但是，您不能通过单个操作访问元素。相反，您可以调用get(i, k)which 返回 的第 k 位，a[i]或者您可以调用swap(i, j)which 交换 的第 i 个和第 j 个元素a[]。设计一个 O(N) 算法来找到丢失的整数。（为简单起见，假设 N 是 2 的幂。）

4

6 回答 6

9

如果 N 是 2 的幂，则可以O(N)使用分治法来完成。

请注意，数字中有logN位。现在，使用此信息 - 您可以结合使用基于分区的选择算法和radix-sort。

  1. 迭代第一位的数字，并将数组分成两半 - 前半部分将此位设为 0，另一半将其设为 1。（swap()用于对数组进行分区）。
  2. 请注意，一半有ceil(N/2)元素，另一半有floor(N/2)元素。
  3. 对较小的数组重复该过程，直到找到丢失的数字。

这种方法的复杂性将是N + N/2 + N/4 + ... + 1 < 2N，所以它是O(n)

于 2012-09-13T10:27:44.267 回答
3

O(N*M)，其中 M 是位数：

N 是 2 的幂，只有一个数字丢失，所以如果你检查每个位，并计算那个位为 0 的数字，并计算 1 的位置，你会得到 2^(M-1) 和 2^ (M-1)-1，较短的属于缺号。有了这个，你可以得到缺失数字的所有位。

于 2012-09-13T09:30:31.913 回答
1

真的不需要使用swap操作！！使用异或！好的，首先你可以计算从 0 到 N 的所有数字的二进制 XOR。所以首先：

long nxor = 0;
for (long i = 0; i <= N; i++)
    nxor = XOR(nxor, i);

然后我们可以计算数组中所有数字的异或，也很简单。让我们称之为 K - 所有数字中的最大位数。

long axor = 0;

long K = 0;
long H = N;
while (H > 0)
{
   H >>= 1; K++;
}

for (long i = 0; i < N - 1; i++)
   for (long j = 0; j < K; k++)
    axor = XOR(axor, get(i,j) << j);

最后你可以计算结果的异或：

long result = XOR(nxor, axor).

顺便说一句，如果 n 是 2 的幂，那么 nxor 值将等于 n ;-)！

于 2012-09-13T11:22:04.647 回答
0

当我们将使用 sum 运算而不是 xor 运算时，您还有另一个答案。请在下面找到代码。

long allsum = n * (n + 1) / 2;
long sum = 0;

long K = 0;
long H = N;
while (H > 0)
{
   H >>= 1; K++;
}

for (long i = 0; i < N - 1; i++)
   for (long j = 0; j < K; k++)
    sum += get(i,j) << j;

long result = allsum - sum.
于 2012-09-13T11:26:39.873 回答
0

假设输入是a[]=0,1,2,3,4,5,7,8，所以6缺少。对数字进行排序只是为了方便，因为不必对它们进行排序以使解决方案起作用。

从那时N起8，数字使用4位表示。从0000到1000。

首先使用最高有效位对数组进行分区。

你得到0,1,2,3,4,5,7和8。由于8存在，请继续使用左侧分区。

使用第二个最高有效位对子数组进行分区。

你得到0,1,2,3和4,5,7。现在继续具有奇数个元素的分区，即4,5,7。

使用第三个最高有效位对子数组进行分区。

你得到4,5和7。再次继续具有奇数个元素的分区，即7.

nothing使用您获得的第 4 个最高有效位和对子数组进行分区7。

所以缺失的数字是6。

另一个例子：

  • a[]=0,1,3,4,5,6,7,8，所以这2是缺失的。
  • 第 1 位分区：0,1,3,4,5,6,7和8，继续0,1,3,4,5,6,7。
  • 第二位分区：0,1,3和4,5,6,7，继续0,1,3（奇数个元素）。
  • 第 3 位分区：0,1和3，继续3（奇数个元素）。
  • 第 4 位分区：nothing和3，因此2丢失。

另一个例子：

  • a[]=1,2,3,4,5,6,7,8，所以这0是缺失的。
  • 第 1 位分区：1,2,3,4,5,6,7和8，继续1,2,3,4,5,6,7。
  • 第二位分区：1,2,3和4,5,6,7，继续1,2,3（奇数个元素）。
  • 第 3 位分区：1和2,3，继续1（奇数个元素）。
  • 第 4 位分区：nothing和1，因此0丢失。

第一个分区进行N操作。第二个分区进行N操作。第三个分区进行N/2操作。第 4 个分区进行N/4操作。等等。

所以运行时间是O(N+N+N/2+N/4+...)=O(N)。

于 2012-09-13T12:52:41.780 回答
0

在没有xor操作的情况下，我们将这样回答这个问题

package missingnumberinarray;
public class MissingNumber 
{
    public static void main(String args[])
    {
        int array1[] = {1,2,3,4,6,7,8,9,10}; // we need sort the array first.
        System.out.println(array1[array1.length-1]);
        int n = array1[array1.length-1];
        int total = (n*(n+1))/2;
        System.out.println(total);
        int arraysum = 0;
        for(int i = 0; i < array1.length; i++)
        {
            arraysum += array1[i];
        }
        System.out.println(arraysum);
        int mis = total-arraysum;
        System.out.println("The missing number in array is "+mis);
    }
}
于 2013-04-30T05:08:07.363 回答