YSMull
<-- home

再做《哪些数字没有出现》

2024/02/04

给定数组A,大小为n,数组元素为1到n的数字,不过有的数字出现了多次,有的数字没有出现。请给出算法和程序,统计哪些数字没有出现,哪些数字出现了多少次。能够在O(n)的时间复杂度,O(1)的空间复杂度要求下完成么？

9年前在微博刷看到这道题，某同学给出的算法让我印象深刻，于是记录在了哪些数字没有出现这篇blog里，最近回顾这道题，发现一下子还看不太懂解法，于是决定用它来考一考同事晴神。

方法一 位运算

旋风小晴天看了这道题，思索片刻后，给出了一个位运算的思路，大致就是，如果数字范围在32位之内，我们就用64位来存储这些数字，那么每个数字的高位32位都是0，就可以用来存储某个数字出现了多少次。对于某个数字 A[i]，就用 A[A[i]] 的空闲的高位来存储 A[i] 出现了多少次，最后对任意的 $k\in[1, n]$，A[k] » 32 就是他出现的次数。

实际操作时，这个解法可以优化一下，我们用低位的32位存储次数，把数字移到高位32位，这样可以简单的用 A[A[i]]++ 来累加数字出现的次数。

public static void main(String[] args) {
    long[] arr = {4, 5, 2, 2, 1, 0};

    // 64位的数字，每个数字移动到高位32位
    for (int i = 0; i < arr.length; i++) {
        arr[i] = arr[i] << 32;
    }

    // 统计每个数字出现的次数
    for (int i = 0; i < arr.length; i++) {
        arr[(int) (arr[i] >> 32)]++;
    }

    // 只取前32位，即低位存储的次数
    for (int i = 0; i < arr.length; i++) {
        arr[i] = arr[i] & 0x00000000FFFFFFFFL;
    }

    // [1, 1, 2, 0, 1, 1]
    System.out.println(Arrays.toString(arr));
}

方法二 n+1进制

然后我把这道题的解法给晴神看了看，并且讲解了算法是如何运行的，结果晴神发现，不用那么复杂的分析，可以用进制的角度去理解那个解法。

因为所有的数字都是小于等于 n 的整数，在 n+1 进制下，这些数字都是个位数，比如0~9的数字，我们可以把所有数字乘以 10，则个位数全部变成了 0。

n+1 进制下，我们把所有数字都乘以 n+1，那么这些数字在 n+1 进制下的个位数就都是 0 了，然后在个位数对这些数字进行累加，这些数字最多出现 n 次，累加也不会进位，最后对 n+1 取模，只保留个位数，就是每个数字出现的次数了

public static void main(String[] args) {
    long[] arr = {4, 5, 2, 2, 1, 0};

    int base = arr.length + 1;

    // 全部移到高位
    for (int i = 0; i < arr.length; i++) {
        arr[i] = arr[i] * base;
    }
    // 在个位数统计数字出现了多少次
    for (int i = 0; i < arr.length; i++) {
        arr[(int) (arr[i] / base)]++;
    }

    // 取模，只保留个位数
    for (int i = 0; i < arr.length; i++) {
        arr[i] = arr[i] % base;
    }

    // [1, 1, 2, 0, 1, 1]
    System.out.println(Arrays.toString(arr));
}

这就是之前那篇 blog 的解法，不需要进行那么复杂的证明和分析，思路一下子就清晰了许多，这样再去看当时记录的解法二，也就清晰了许多。