題目:
給你一個下標從 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 。
思路:
簡單哈希。
代碼:
class Solution {public int[] findMissingAndRepeatedValues(int[][] grid) {int n = grid.length * grid.length + 1;int[] cnt = new int[n];for(int i = 0; i < grid.length; i++){for(int j = 0; j < grid[0].length; j++){cnt[grid[i][j]]++; }}int[] ans = new int[2];for(int i = 0; i < n; i++){if(cnt[i] > 1){ans[0] = i;}if(cnt[i] == 0){ans[1] = i;}}return ans;}
}