从零学算法2965

2965. 找出缺失和重复的数字
给你一个下标从 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

• 最简单的，用数组统计每个数出现的次数，然后遍历数组即可

•   public int[] findMissingAndRepeatedValues(int[][] grid) {int n = grid.length;int[] res = new int[2];int[] temp = new int[n * n + 1];for(int[] g : grid){for(int x : g){temp[x]++;}}for(int i = 1; i < temp.length; i++){if(temp[i] == 0)res[1] = i;else if(temp[i] == 2)res[0] = i;}return res;}
  

• 数学方法：由于 a 出现两次，b 出现 0 次，所以当所有数相加时会得到 1+2+…+n + a - b，也就是说把数组中的所有数相加减去 1~n² 之和就能得到 d1 = a - b 。将所有数的平方和相加也是同理，减去 1~n² 的平方后就会剩下 d2 = a²-b²=(a+b)(a-b)，最终我们可以得到 a - b = d1, a + b = d2 / d1，那么 a 和 b 就很容易计算了
• 令 m = n²，$1-m之和=\frac{m(1+m)}{2}$
• $1-m的平方和=\frac{m(m+1)(2m+1)}{6}$

•   public int[] findMissingAndRepeatedValues(int[][] grid) {int n = grid.length;int m = n * n;int[] res = new int[2];int d1 =  -m * (1 + m) / 2;long d2 = (long) -m * (m + 1) * (2 * m + 1) / 6;for(int[] row : grid){for(int x : row){d1 += x;d2 += x * x;}}int d = (int) (d2 / d1);res[0] = (d + d1) / 2;res[1] = (d - d1) / 2;return res;}
  

• 位运算：如果我们额外加入 1 ~ m，最终会得到一个数出现 1 次，一个数出现 3 次，其余数出现两次，而异或后出现 1 次和出现 3 次是一样，即这些数的异或和就为 a^b，那么就相当于第 260 题了，从一堆出现两次的数字中找到只出现一次的两个数字。
• 额外计算 1 到 n² 的异或和时，可以不遍历 1 ~ n 而用 O(1) 的计算公式
  的异或和

•   public int[] findMissingAndRepeatedValues(int[][] grid) {int n = grid.length;int m = n * n;int or = 0;for(int[] row : grid){for(int x : row){or ^= x;}}or ^= n % 2 > 0 ? 1 : m;// 计算 or 最低位的 1 后面有几个 0// 下面会根据右移 one 位来分组// 其实核心思想还是根据 or 中为 1 的某一位来分类// 所以也可以按照第 260 题的写法令 one 为 xx1x// 下面分组就能按照 x & one 是否等于 0 来分组int one = Integer.numberOfTrailingZeros(or);int[] res = new int[2];// 以下两个循环都是为了把数组中的数以及额外的 1~m 按照// 对应于 one 的那一位为 0 还是 1 分类异或进结果数组// 反正重复的数都会被异或掉，所以最终数组会剩下 a 和 bfor(int x = 1; x <= m; x++){res[(x >> one) & 1] ^= x;}for(int[] row : grid){for(int x : row){res[(x >> one) & 1] ^= x;}}// 由于我们无法区分 res 中哪个是 a 哪个是 b// 所以我们根据数组中只存在 a 没有 b 来判断// 如果数组中某个数等于 res[0] 说明 res[0] 就是 a// 那么可以直接返回for (int[] row : grid) {for (int x : row) {if (x == res[0]) {return res;}}}return new int[]{res[1], res[0]};}