这看起来很相似，但与旧问题不同 . 给定大小为n的数组（允许重复的数字），找到缺少的2个数字[重复]-Java 学习之路

可能重复：简单的面试问题变得更难：给出数字1..100，找到丢失的数字

**不，这是重复!!!给定数组中的某些数字可能会重复 . 请参阅我帖子底部的示例 . 谢谢！！！ **

给定大小为n的数组，包含1到n范围内的数字 . 除2个数字外，每个数字至少出现一次 . 找到丢失的数字 .

例如A = [2,4,5,4,6,5]，缺失的数字是3和1 .

我的解决方案

用O（n lg n）排序A然后扫描 .

或者，扫描并设置新的bool阵列B以标记给定阵列中的数字是否出现，例如， B [A [i]] =真或假 . 然后，将bool数组扫描到其索引为缺少元素的false元素 . 时间O（n）但是空间O（n） .

是否有O（n）的时间和O（1）的空间解？

Attention: 求和和乘法的方法不起作用 .

例如，给定A [2,3,2,3]，缺失的数字是：1和4 .

假设缺少的数字是x和y .

我们不能得到：

x y = 1到n之和 - A之和

x * y = 1至n的乘积/ A的乘积

1 4！= 10 - 10

1 * 4！= 24/36

谢谢

2 回答

0

如果数据未排序，则无法确保在不查看每个值的情况下找到缺失的值 . 所以，最坏的情况是O（n）找到它们 . 要确定哪些缺失，可以在O（1）中通过计算 n 和 sum(1..n) 的阶乘并除去乘积并从每个项中减去总和来实现 . 最后你会通过求解 a + b = remaining sum 和 a * b = remaining product 来了解哪些是遗漏的 . 这是一个骗子，因为你实际上是在进行初步的O（n）计算，或者是一个具有空间影响的表查找 .

回复于 2024-04-27T06:44:43+08:00
2
codekaizen的想法可以调整，使其可行：

计算U =所有元素的总和，V =所有元素的平方和 .
如果a和b是缺失的元素，我们有
```
a + b = n(n+1)/2 - U = W, say
a^2 + b^2 = n(n+1)(2n+1)/6 - V = X, say
```
替代b = W - 在第二个等式中得到a
```
a^2 + (W - a)^2 = X
```
这是a中的二次方程，您可以解决 .
回复于 2024-04-27T06:44:43+08:00