日期: 2024 年 5 月 31 日

目标

给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n2] 范围内。除了 a 出现 两次，b 缺失 之外，每个整数都 恰好出现一次 。

任务是找出重复的数字a 和缺失的数字 b 。

返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。

示例 1：

输入：grid = [[1,3],[2,2]]
输出：[2,4]
解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。

示例 2：

输入：grid = [[9,1,7],[8,9,2],[3,4,6]]
输出：[9,5]
解释：数字 9 重复，数字 5 缺失，所以答案是 [9,5] 。

说明：

• 2 <= n == grid.length == grid[i].length <= 50
• 1 <= grid[i][j] <= n * n
• 对于所有满足 1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。
• 对于所有满足 1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。
• 除上述的两个之外，对于所有满足 1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x 。

思路

记录元素的出现次数，选出其中出现次数为2和0的值即可。

网友还给出了一些位运算与数学公式求解的方法，可以降低空间复杂度，不用对每个元素计次，而是使用异或和与数学公式求解。

异或和求解的关键是如何区分得到的 a ^ b，由于a 与 b 不同，异或的结果至少有一个非0位，可以根据该bit位分组，这样每一组中就只含有a或b。

至于数学公式求解的关键是，通过各项和的差可以得到 b - a，各项平方和的差可以得到 b^2 - a^2，进而求得 b + a，解方程组可得a、b。

代码

/**
 * @date 2024-05-31 0:12
 */
public class FindMissingAndRepeatedValues2965 {

/**
     * 公式求和 1，2，……，n^2 以及 1^2，2^2，……，n^2
     * 然后遍历求和，二者之差为b - a 和 b^2 - a^2
     * 进而可以求得b + a，解方程可得a、b
     */
    public int[] findMissingAndRepeatedValues_v2(int[][] grid) {
        int n = grid.length;
        int n2 = n * n;
        long sum = 0;
        long sum2 = 0;
        for (int[] row : grid) {
            for (int i : row) {
                sum += i;
                sum2 += i * i;
            }
        }
        long bsuba = n2 * (n2 + 1L) / 2 - sum;
        long b2suba2 = n2 * (n2 + 1L) * (2 * n2 + 1) / 6 - sum2;
        long badda = b2suba2 / bsuba;
        long b = (badda + bsuba) / 2L;
        long a = badda - b;
        return new int[]{(int) a, (int) b};
    }

    /**
     * 异或和
     */
    public int[] findMissingAndRepeatedValues_v1(int[][] grid) {
        int n = grid.length;
        int n2 = n * n;
        int prefix = 0;
        for (int i = 1; i <= n2; i++) {
            prefix ^= i;
        }
        int tmp = 0;
        for (int[] row : grid) {
            for (int element : row) {
                tmp ^= element;
            }
        }
        int axorb = prefix ^ tmp;
        int shift = Integer.numberOfTrailingZeros(axorb);
        int[] res = new int[2];
        // 由于axorb至少有1bit是不同的，那么根据该bit分组，这样每一组里面a b是分开的
        for (int i = 1; i <= n2; i++) {
            res[i >> shift & 1] ^= i;
        }
        for (int[] row : grid) {
            for (int element : row) {
                res[element >> shift & 1] ^= element;
            }
        }
        // 由于顺序是不确定的，判断出现的为a
        for (int[] row : grid) {
            for (int element : row) {
                if (element == res[0]){
                    return res;
                }
            }
        }
        // 调换位置
        return new int[]{res[1], res[0]};
    }

    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int l = m * n + 1;
        int[] occurrence = new int[l];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                occurrence[grid[i][j]]++;
            }
        }
        int[] res = new int[2];
        for (int i = 1; i < l; i++) {
            if (occurrence[i] == 0) {
                res[1] = i;
            } else if (occurrence[i] == 2) {
                res[0] = i;
            }
        }
        return res;
    }
}

性能