这看起来与旧问题相似但有所不同。给定一个大小为 n 的数组（允许重复的数字），找到缺失的 2 个数字

Question

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

**不，它是重复的！给定数组中的某些数字可能是重复的。请参考我帖子底部的示例。谢谢 ！！！ **

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

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

我的解决方案：

用O(n lg n)对A进行排序，然后扫描。

或者，扫描并建立一个新的布尔数组B来标记给定数组中的数字是否出现，例如B[A[i]] = true或false。然后，扫描 bool 数组，找到索引为缺失元素的 false 元素。时间 O(n) 但空间 O(n)。

是否存在时间 O(n) 和空间 O(1) 的解？

注意： 加法和乘法的方法不起作用。

例如，给定 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

谢谢

Answer 1

如果数据未排序，则无法确保您无需查看每个值即可找到缺失值。因此，最坏的情况是找到它们的时间复杂度为 O(n)。要确定缺少哪些内容，您可以通过计算 n 和 sum(1..n) 的阶乘并除以乘积和从您遇到的每个术语的总和中减去。最后，您可以通过求解 a + b = 剩余总和 和 a * b = 剩余产品 来知道缺少哪些内容。但这是一个作弊行为，因为您实际上是在进行初步的 O(n) 计算，或者进行具有空间影响的表查找。

Answer 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 的二次方程，您可以求解。