在线性时间和常量空间内查找数组中的缺失和重复元素

Question

你将得到一个包含 N 个 64 位整数的数组，其中 N 可能非常大。你知道除了一个整数缺失和一个整数重复外，1..N 中的每个整数都出现一次。

编写一个线性时间算法，查找缺失和重复的数字。此外，您的算法应在小恒定空间内运行，并保持数组不变。

来源：http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/

- KushalP

---

我认为你会发现这个链接很有帮助：https://dev59.com/dXA75IYBdhLWcg3wDUq2 - Jim Mischel

@JIm：实际上那是不同的。在这里，我们得到的方程形式为sum a^k - sum b^k = s，而那个是sum a^k + sum b^k = s，允许我们使用牛顿恒等式。看起来似乎不明显我们是否也可以在这里使用这些牛顿恒等式。事实上，这更相关：https://dev59.com/oG435IYBdhLWcg3wuikn - Aryabhatta

@Moron：这就是为什么我说我认为他会发现它有帮助，而不是投票关闭问题作为重复的原因。 - Jim Mischel

@Jim：我是在说它可能没有人们想象的那么有帮助。我并没有谈论重复或其他什么。无论如何... - Aryabhatta

Answer 1

如果数组中存在所有数字，总和将是 N(N+1)/2。

通过在O(n)中将数组中的所有数字相加来确定实际总和，让这个值为Sum(Actual)。

一个数字缺失，让它是j，一个数字重复，让它是k。这意味着

Sum(Actual)=N(N+1)/2 + k - j

由此得出

k = Sum(Actual) -N(N+1)/2 + j

我们还可以计算数组中平方数的总和，如果存在所有数字，则总和将为n³/3+n²/2+n/6。

现在我们可以在O(n)中计算实际平方和，让这个值为Sum(Actual Squares)。

Sum(Actual Squares)=n³/3+n²/2+n/6+k²-j²

现在我们有两个方程式，可以确定j和k。

- BrokenGlass

---

不错的分析。我将其推广到了m<N个未知数。 - DavidC

由于“N可能非常大”，因此需要BigInt支持。 - Abhinav Gauniyal

Answer 2

XOR技巧使用只读数组进行两次操作。

这避免了求和及平方和解决方案可能出现的整数溢出问题。

假设两个数字是x和y ，其中一个是缺失的数字，另一个重复出现。

对数组中的所有元素以及1,2,...,N进行异或运算。

结果为w = x XOR y 。

现在，由于x和y是不同的，因此w不为零。

选择任意非零位的w。 x和y在此位上不同。 假设该位的位置为k。

现在考虑将数组（和数字1,2,…,N）拆分为两个集合，基于位k是否为0或1来分割。

现在，如果我们分别计算两个集合中元素的XOR运算，结果就会是x和y。

由于分裂的标准只是检查位是否设置，因此我们可以通过对数组进行另一次遍历，并具有两个变量，每个变量都保存迄今为止已看到的元素（和1,2,…,N）的XOR，来计算两个集合的两个XOR。 当我们完成时，这两个变量将保存x和y。

相关内容：

• 查找数组中缺失的元素，可以将其推广为出现两次和缺失的m个元素。

查找仅出现一次的三个数字，这篇文章是关于三个缺失数字的。

- Aryabhatta

---

有没有一本理论/书籍可以详细阐述这个问题？ - user248884

Answer 3

使用与相关面试问题类似的基本思想，您可以执行以下操作：

• Sum up all the numbers (we shall call this S1) and their squares (S2)
• Compute the expected sum of the numbers, without modifications, i.e. E1 = n*(n+1)/2 and E2 = n*(n+1)*(2n+1)/6
• Now you know that E1 - S1 = d - m and E2 - S2 = d^2 - m^2, where d is the duplicated number and m the missing one.

• Solve this system of equations and you'll find that:

  m = 1/2 ((E2 - S2)/(E1 - S1) - (E1 - S1))
  d = 1/2 ((E2 - S2)/(E1 - S1) + (E1 - S1)) // or even simpler: d = m + (E1 - S1)
  

.

$S1 = $S2 = 0;
foreach ($nums as $num) {
    $S1 += $num;
    $S2 += $num * $num;
}

$D1 = $n * ($n + 1) / 2                - $S1;
$D2 = $n * ($n + 1) * (2 * $n + 1) / 6 - $S2;

$m = 1/2 * ($D2/$D1 - $D1);
$d = 1/2 * ($D2/$D1 + $D1);

- NikiC

---

如果数字是1..n而不是1..100，那么它实际上并不是O(n)。 - IVlad

@IVlad：为什么不是呢？循环n次的时间复杂度是O(n)，其他计算的时间复杂度都是O(1)。 - NikiC

@nikic - 由于添加 n 个64位数字的结果不一定是一个64位数字，因此您需要编写处理这样大整数的代码。该代码将无法在恒定时间内运行。平方 n 也不是 O(1)-请注意，n 没有上限。并不是说您的解决方案是错误的，我并不认为在 OP 的约束条件下可以做到这一点，我只是说它不是线性的。 - IVlad

@IVlad：我看不出什么问题。你需要常量191位比特用于平方和，以及128位比特用于普通和。 - NikiC

@IVlad 将64位数字相加或相乘（平方）的操作是恒定时间。这种操作的结果最多是128位数字，将所有可能的128位数字相加的结果最多是256位数字。存在一个256位数字的恒定上限，并且由于对这些数字进行操作所需的时间与数字的长度有关，而数字的长度有已知的上限，因此它是一个恒定的操作。 - corsiKa

我认为你可以使用模算术完全消除对64位的需求... - R.. GitHub STOP HELPING ICE

Answer 4

这是一个基于 @Aryabhatta 的想法的Java实现：
输入：[3 1 2 5 3]
输出：[3, 4]

public ArrayList<Integer> repeatedNumber(final List<Integer> A) {
    ArrayList<Integer> ret = new ArrayList<>();
    int xor = 0, x = 0, y = 0;
    for(int i=0; i<A.size(); i++) {
        xor ^= A.get(i);
    }
    for(int i=1; i<=A.size(); i++) {
        xor ^= i;
    }

    int setBit = xor & ~(xor-1);
    for(int i=0; i<A.size(); i++) {
        if((A.get(i) & setBit) != 0) {
            x ^= A.get(i);
        } else {
            y ^= A.get(i);
        }
    }
    for(int i=1; i<=A.size(); i++) {
        if((i & setBit) != 0) {
            x ^= i;
        } else {
            y ^= i;
        }
    }

    for(int i=0; i<A.size(); i++) {
        if(A.get(i) == x) {
            ret.add(x);
            ret.add(y);
            return ret;
        } 

        if(A.get(i) == y) {
            ret.add(y);
            ret.add(x);
            return ret;
        }
    }

    return ret;
}

- spiralmoon

Answer 5

采用“保持数组不变”的要求（即只要在最后不改变数组，暂时修改数组是可以的），可以提出一个面向编程的解决方案。我假设数组大小N远小于2^64，这是一种完全不现实的内存量。因此，我们可以安全地假设N < 2^P，其中P << 64（明显小得多）。换句话说，这意味着数组中的所有数字都有一些未使用的高位。因此，让我们将最高位作为标志，表示该位置的索引是否在数组中已经出现过。算法如下：

 set HIGH = 2^63  // a number with only the highest bit set
 scan the array, for each number k do
   if array[k] < HIGH: array[k] = array[k] + HIGH // set the highest bit
   else: k is the duplicate
 for each i in 1..N do
   if array[i] < HIGH: i is missing
   else: array[i] = array[i] - HIGH // restore the original number

这是线性时间和计算量非常小的操作。

- davka

Answer 6

BrokenGlass提出的解决方案涵盖了两个未知数的情况（对应一个重复数字和一个缺失数字），使用两个公式：

并且

这些公式分别给出了-1和-2阶的广义调和数，使用幂级数。

通过包含-3阶广义调和数的值，可以将此解扩展到3个未知数的情况。

为了解决未知数（重复和缺失数字）的数量，使用-1到-m的n阶广义调和数的m个。

---

笨蛋指出，这种方法早在StackOverflow上就已经讨论过了，链接为Easy interview question got harder。

- DavidC

---

谐和数是指形如1+ 1/2 + 1/3 + ... + 1/n的数列。 - Aryabhatta

这些似乎只定义在m >= 1时才有意义，但你所说的是有道理的。这里提供另一个参考链接：http://mathworld.wolfram.com/PowerSum.html。请查看方程式11。 - Aryabhatta

@Moron 通用调和数允许m<0。在Mathematica中尝试运行Table[HarmonicNumber[10, -m], {m, 1, 7}]或Sum[p^k, {p, 1, n}]。感谢提供PowerSum的链接，它似乎也很适合。 - DavidC

顺便说一句，你的答案缺少使用牛顿恒等式来形成我们寻找根的多项式。此外，这个问题的概括已经在这里处理过了：https://dev59.com/dXA75IYBdhLWcg3wDUq2 - Aryabhatta

@Davidпјҡе®һйҷ…дёҠжҲ‘еҲҡж„ҸиҜҶеҲ°пјҢзүӣйЎҝжҒ’зӯүејҸ并дёҚзӣҙжҺҘйҖӮз”ЁдәҺиҝҷз§ҚеҪўејҸзҡ„ж–№зЁӢпјҡ\sum (x_i)^k - \sum (y_i)^k = P_kгҖӮGroebner еҹәжҳҜдёҖз§Қж–№жі•пјҢжҲ–иҖ…дҪ еҸҜд»ҘжҺЁе№ҝжҲ‘зҡ„зӯ”жЎҲеңЁиҝҷйҮҢпјҡhttps://dev59.com/questions/oG435IYBdhLWcg3wuikn#5251995 - Aryabhatta

Answer 7

    long long int len = A.size();
    long long int sumOfN = (len * (len+1) ) /2, sumOfNsq = (len * (len +1) *(2*len +1) )/6;
    long long int missingNumber1=0, missingNumber2=0;

    for(int i=0;i<A.size(); i++){
       sumOfN -= (long long int)A[i];
       sumOfNsq -= (long long int)A[i]*(long long int)A[i];
    }

    missingno = (sumOfN + sumOfNsq/sumOfN)/2;
    reaptingNO = missingNumber1 - sumOfN;

- Bharat Arya

Answer 8

假设集合已排序的伪代码

missing = nil
duplicate = nil

for i = 0, i < set.size - 1, i += 1
  if set[i] == set[i + 1]
    duplicate = set[i]
  else if((set[i] + 1) != set[i+1])
    missing = set[i] + 1
  if missing != nil && duplicate != nil
    break

return (missing, duplicate)

- dan.simpson

---

几乎可以肯定你不能假设数组已经排好序。 - BrokenGlass