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

Question

可能重复：
找到两个缺失的数字

我想了一会儿，似乎无法得到答案......所以除了由给定数组。如何在 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

然后你也可以做同样的事情，例如，乘法并得到：

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

在你的情况下：

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

所以答案是 2 和 5。

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