2965. Find Missing and Repeated Values 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;

        int xor = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                xor ^= grid[i][j];
                xor ^= i * n + j + 1;
            }
        }

        int mask = Integer.lowestOneBit(xor);

        int a = 0, b = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if ((mask & grid[i][j]) != 0) {
                    a ^= grid[i][j];
                } else {
                    b ^= grid[i][j];
                }
                if ((mask & (i * n + j + 1)) != 0) { // 注意此处需要加 1, 因为值的范围为 [1, n^2]
                    a ^= i * n + j + 1;
                } else {
                    b ^= i * n + j + 1;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == a) {
                    return new int[]{a, b};
                }
            }
        }

        return new int[]{b, a};
    }
}

References

2965. Find Missing and Repeated Values