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

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/

Answer 1

如果数组中存在所有数字,那么总和就是N(N+1)/2.

通过在O(n)中对数组中的所有数字求和来确定实际总和,这就是Sum(Actual).

缺少一个数字,让这个j和一个数字重复,让这个k.这意味着

总和(实际)= N(N + 1)/ 2 + k-j

源于此

k =总和(实际)-N(N + 1)/ 2 + j

此外,我们可以计算在阵列中平方的总和,这将总结为n ³ /3 + N ² /2 + N/6,如果所有数字是本.

现在我们可以计算O(n)中的实际平方和,让它成为Sum(Actual Squares).

总和(实际方)= N ³ /3 + N ² /2 + N/6 + K ² - J ²

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

Answer 2

XOR技巧使用只读数组进行两次传递.

这避免了可能的整数溢出问题,求和和解的总和.

让这两个数字是x和y,其中之一是缺少的数量和其他重复.

XOR的所有元素,以及1,2,...,N.

结果是w = x XOR y.

现在既然x又y不同,w就是非零.

选择任何非零位w.x并且y在这一点上有所不同.说位的位置是k.

现在考虑将数组(和数字1,2,...,N)分成两组,基于位置k的位是0还是1.

现在,如果我们计算两组元素的XOR(单独),结果必须是x和y.

由于分裂的标准只是检查是否设置了一个位,我们可以通过再次通过数组并有两个变量来计算两个集合中的两个XOR,每个变量都包含到目前为止看到的元素的XOR. (和1,2,...N),每组.最后,当我们完成时,这两个变量将保持x和y.

有关:

• 找到数组中缺少的元素,可以推广到m出现两次,m缺失.

• 找到三个数字只出现一次,大约三个缺失.

Answer 3

使用相关面试问题的基本思路,你可以做到:

• 总结所有数字(我们称之为S1)和它们的方块(S2)
• 计算预期的数字总和,无需修改,即E1 = n*(n+1)/2和E2 = n*(n+1)*(2n+1)/6
• 现在你知道,E1 - S1 = d - m和E2 - S2 = d^2 - m^2,其中d是重复的次数和m丢失的一个.

• 解决这个方程组,你会发现:

  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);

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;
}