11

我们有一台内存为 O(1) 的机器，我们想在第一遍n中（一个接一个）传递数字，然后我们排除这两个数字，然后将n-2数字传递给机器。

编写一个查找缺失数字的算法。

4

7 回答 7

11

它可以用 O(1) 内存来完成。

您只需要几个整数来跟踪一些运行总和。整数不需要 log n 位（其中 n 是输入整数的数量），它们只需要 2b+1 位，其中 b 是单个输入整数中的位数。

当您第一次阅读流时，添加所有数字及其所有平方，即对于每个输入数字 n，请执行以下操作：

sum += n
sq_sum += n*n

然后在第二个流上对两个不同的值 sum2 和 sq_sum2 执行相同的操作。现在做以下数学：

sum - sum2 = a + b
sq_sum - sq_sum2 = a^2 + b^2

(a + b)(a + b) = a^2 + b^2 + 2ab
(a + b)(a + b) - (a^2 + b^2) = 2ab
(sum*sum - sq_sum) = 2ab

(a - b)(a - b) = a^2 + b^2 - 2ab
               = sq_sum - (sum*sum - sq_sum) = 2sq_sum - sum*sum
sqrt(2sq_sum - sum*sum) = sqrt((a - b)(a - b)) = a - b
((a + b) - (a - b)) / 2 = b
(a + b) - b = a

在所有中间结果中都需要 2b+1 位，因为您要存储两个输入整数的乘积，并且在一种情况下将其中一个值乘以 2。

于 2012-04-19T06:43:39.283 回答
3

假设数字范围为 1..N 并且其中 2 个缺失 -x并且y，您可以执行以下操作：

使用高斯公式：sum = N(N+1)/2

sum - actual_sum = x + y

使用数字的乘积：product = 1*2..*N = N!

product - actual_product = x * y

解决 x,y 并且您有丢失的数字。

简而言之-遍历数组并将每个元素相加得到actual_sum，将每个元素相乘得到actual_product。然后求解 的两个x方程y。

于 2012-04-18T22:13:03.927 回答
3

它不能用O(1)内存来完成。

假设您有恒定k的内存位 - 那么您2^k的算法可以有可能的状态。

但是 - 输入不受限制，并且假设对于不同的问题情况有(2^k) + 1可能的答案，根据piegeonhole 原则，对于具有不同答案的 2 个问题，您将返回相同的答案两次，因此您的算法是错误的。(2^k) + 1

于 2012-04-18T22:14:50.087 回答
2

当我读完这个问题时，我想到了以下内容。但是上面的答案表明，使用 O(1) 内存是不可能的，或者应该对数字范围进行限制。如果我对问题的理解有误，请告诉我。好的，这就去

你有O(1)内存 - 这意味着你有恒定的内存量。

当n 个数字第一次传递给您时，只需继续将它们添加到一个变量中并继续将它们相乘到另一个变量中。因此，在第一遍结束时，您将获得 2 个变量S1和P1中所有数字的总和和乘积。到目前为止，您已经使用了 2 个变量（如果您读取内存中的数字，则为 +1）。

当第二次将(n-2) 个数字传递给您时，请执行相同操作。将(n-2) 个数字的总和和乘积存储在 2 个其他变量S2和P2中。到目前为止，您已经使用了 4 个变量（如果您读取内存中的数字，则 +1）。

如果两个缺失的数字是x和y，那么

x + y = S1 - S2
x*y = P1/P2;

您在两个变量中有两个方程。解决它们。

因此，您使用了恒定数量的内存（与 n 无关）。

于 2012-04-19T06:42:17.117 回答
1 
void Missing(int arr[], int size)
{
  int xor = arr[0]; /* Will hold xor of all elements */
  int set_bit_no;  /* Will have only single set bit of xor */
  int i;
  int n = size - 2;
  int x = 0, y = 0;

  /* Get the xor of all elements in arr[] and {1, 2 .. n} */
  for(i = 1; i < size; i++)
    xor ^= arr[i];  
  for(i = 1; i <= n; i++)
    xor ^= i;   

  /* Get the rightmost set bit in set_bit_no */
  set_bit_no = xor & ~(xor-1);

  /* Now divide elements in two sets by comparing rightmost set
   bit of xor with bit at same position in each element. */
  for(i = 0; i < size; i++)
  {
    if(arr[i] & set_bit_no)
      x = x ^ arr[i]; /*XOR of first set in arr[] */
    else
      y = y ^ arr[i]; /*XOR of second set in arr[] */
  }
  for(i = 1; i <= n; i++)
  {
    if(i & set_bit_no)
      x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/
    else
      y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */
  }

  printf("\n The two repeating missing elements are are %d & %d ", x, y);
}
于 2016-06-21T19:41:25.497 回答
0

请查看下面的解决方案链接。它解释了 XOR 方法。这种方法比上面解释的任何方法都更有效。它可能与上面的 Victor 相同，但有一个解释为什么会这样。

解决方案在这里

于 2018-09-05T22:24:28.017 回答
0

这是不需要任何二次公式或乘法的简单解决方案：

假设 B 是两个缺失数字的总和。

两个缺失数字的集合将来自：(1,B-1),(2,B-1)...(B-1,1)

因此，我们知道这两个数字之一将小于或等于 B 的一半。

我们知道我们可以计算 B（两个缺失数字的总和）。

因此，一旦我们有了 B，我们将找到列表中小于或等于 B/2 的所有数字的总和，然后从 (1 到 B/2) 的总和中减去该总和，得到第一个数字。然后，我们通过从 B 中减去第一个数字得到第二个数字。在下面的代码中，rem_sum 是 B。

public int[] findMissingTwoNumbers(int [] list, int N){
    if(list.length == 0 || list.length != N - 2)return new int[0];

    int rem_sum = (N*(N + 1))/2;
    for(int i = 0; i < list.length; i++)rem_sum -= list[i];

    int half = rem_sum/2;
    if(rem_sum%2 == 0)half--; //both numbers cannot be the same
    int rem_half = getRemHalf(list,half);

    int [] result = {rem_half, rem_sum - rem_half};
    return result;
}
private int getRemHalf(int [] list, int half){
    int rem_half = (half*(half + 1))/2;
    for(int i = 0; i < list.length; i++){
        if(list[i] <= half)rem_half -= list[i];
    }
    return rem_half;
}
于 2020-06-07T18:09:00.553 回答