在线性时间和常量空间中查找数组中缺少的和重复的元素-Java 学习之路

你得到一个 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/

7 回答

26

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

通过在O（n）中对数组中的所有数字求和来确定实际总和，让它为 Sum(Actual) .

缺少一个数字，让它为 j 并且一个数字是重复的，让它为 k . 这意味着

总和（实际）= N（N 1）/ 2 k - j

源于此

k =总和（实际）-N（N 1）/ 2 j

我们还可以计算数组中的平方和，如果所有数字都存在，则总和为n3 / 3 n2 / 2 n / 6 .

现在我们可以用O（n）计算实际的平方和，让它为 Sum(Actual Squares) .

总和（实际平方）= n3 / 3 n2 / 2 n / 6 k2 - j2

现在我们有两个方程式，我们可以用它来确定 j 和 k .

回复于 2024-04-20T05:00:42+08:00
6
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 .

有关：
- Finding missing elements in an array可以推广到m出现两次，m缺失 .
- Find three numbers appeared only once这大概是三个失踪 .
回复于 2024-04-20T05:00:42+08:00
3
使用related interview question的基本思路，你可以做到：
- 总结所有数字（我们称之为 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);
```
回复于 2024-04-20T05:00:42+08:00

这是基于@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;
}

回复于 2024-04-20T05:00:42+08:00

3

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

和

这些公式分别产生-1和-2的n阶的generalized harmonic number . （电源系列）

通过包括阶数n为-3的广义谐波数的值，该解可以推广到3个未知数 .

要求解m个未知数（重复数和缺失数），请使用阶数n为-1到-m的m个广义谐波数 .

Moron指出，这种方法早先在StackOverflow中讨论过Easy interview question got harder .

回复于 2024-04-20T05:00:42+08:00
36
从字面上考虑 leave the array untouched 要求（即，只要最终不改变就可以暂时修改数组），可以建议面向编程的解决方案 .

我假设数组大小 N 远小于 2^64 ，这是一个完全不切实际的内存量 . 所以我们可以安全地假设 N < 2^P 这样 P << 64 （明显更小） . 换句话说，这意味着数组中的 all 数字有一些 high bits unused . 因此，让我们只使用最高位作为标志，是否已在数组中看到该位置的索引 . 算法如下：
```
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
```
这是线性时间和非常少的计算
回复于 2024-04-20T05:00:42+08:00

-2

Psuedo代码假设集合已排序

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)

回复于 2024-04-20T05:00:42+08:00

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

7 回答

相关问题