找到两个缺少的数字-Java 学习之路

有一台机器有O（1）内存 . 我们想要第一次传递n个数字（逐个），我们再次排除两个数字，我们将n-2传递给机器 . 写一个找到缺失数字的算法 . 这是一个面试问题，我无法解决 .

6 回答

2
It can be done with O(1) memory.

您只需要几个整数来跟踪一些运行总和 . 整数不需要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 .
回复于 2024-05-17T21:25:05+08:00
11
假设数字的范围是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 的两个方程式 .
回复于 2024-05-17T21:25:05+08:00
3

It cannot be done with O(1) memory.

假设您有一个常量 k 位的内存 - 那么您的算法可以有 2^k 个可能的状态 .

但是 - 输入不受限制，并假设 (2^k) + 1 可能有 (2^k) + 1 个问题的答案，从piegeonhole principle开始，对于不同答案的2个问题，您将返回两次相同的答案，因此您的算法错误 .

回复于 2024-05-17T21:25:05+08:00
0
一读完这个问题，我就想到了以下内容 . 但上面的答案表明，O（1）内存是不可能的，或者应该对数字范围有约束 . 告诉我，如果我对这个问题的理解是错误的 . 好的，所以这里

你有 O(1) 记忆 - 这意味着你有 constant amount of memory .

当 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） .
回复于 2024-05-17T21:25:05+08:00

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);
}

回复于 2024-05-17T21:25:05+08:00

3

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

Solution here

回复于 2024-05-17T21:25:05+08:00

找到两个缺少的数字

6 回答

相关问题