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]};}