arrays - 包含 n-2 个整数 1 到 n 的数组，O(n) 算法如何用 O(1) 额外空间查找缺失的 2 个数字？

Question

Possible Duplicate:
Find two missing numbers

我思考了一段时间，似乎无法得到这个问题的答案...所以一个数组，其中包含 n-2 个唯一整数，范围从 1 到 n，并且除了空间之外还有 O(1) 空间给出了数组所使用的。如何在 O(n) 时间内找到数组中缺失的从 1 到 n 的两个整数？

例如，a = [4,3,1,6] 和 O(1) 额外空间 如何在 O(n) 时间内找到 2、5？

Answer 1

这里有一个想法:只需保留一些统计数据即可为您提供有关缺失数字的信息。例如，如果您将所有数字的总和计算为 S，则:

(1+2+..+N) - S = a+b

其中 a 和 b 是缺失的数字。在您的示例中，您将得到:

1+2+3+4+5+6 - 4+3+1+6 = 7 = a+b

然后您也可以执行相同的操作，例如，对于乘法和 get:

(1*2*..*N) / S = a*b

就你的情况而言:

(1*2*3*4*5*6) / 72 = 10 = a*b

所以答案是 2 和 5。

基本上有很多统计数据可以通过这种方式使用......