Easy

题目描述

给你一个下标从 0 开始、大小为 n x n 的二维整数矩阵 grid，其中的值在范围 [1, n²] 内。除了 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²
  • 除了一个数字出现两次，一个数字缺失外，[1, n²] 范围内的每个整数都恰好出现一次。

解题思路

这道题要求找出一个 n×n 矩阵中重复出现的数字和缺失的数字。我们可以用多种方法来解决：

方法一：哈希表统计 最直观的方法是使用哈希表统计每个数字的出现次数。遍历矩阵中所有元素，记录每个数字出现的次数。然后遍历 [1, n²] 范围内的所有数字，找出出现次数为 2 的数字（重复数字）和出现次数为 0 的数字（缺失数字）。

方法二：数学方法 我们可以利用数学性质来解决。设重复数字为 a，缺失数字为 b。

  • 期望和：1 + 2 + … + n² = n²(n²+1)/2
  • 实际和：矩阵中所有元素的和
  • 差值：实际和 - 期望和 = a - b

通过这个等式以及其他约束条件，可以求出 a 和 b。

方法三：原地标记 由于数字范围是 [1, n²]，我们可以利用数组下标来标记数字是否出现过。

推荐使用方法一，因为它简单直观，代码易懂，时间复杂度也是最优的。

代码实现

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        unordered_map<int, int> count;
        
        // 统计每个数字出现的次数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                count[grid[i][j]]++;
            }
        }
        
        int repeated = -1, missing = -1;
        
        // 找出重复和缺失的数字
        for (int i = 1; i <= n * n; i++) {
            if (count[i] == 2) {
                repeated = i;
            } else if (count[i] == 0) {
                missing = i;
            }
        }
        
        return {repeated, missing};
    }
};

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        count = {}
        
        # 统计每个数字出现的次数
        for i in range(n):
            for j in range(n):
                num = grid[i][j]
                count[num] = count.get(num, 0) + 1
        
        repeated = missing = -1
        
        # 找出重复和缺失的数字
        for i in range(1, n * n + 1):
            if count.get(i, 0) == 2:
                repeated = i
            elif count.get(i, 0) == 0:
                missing = i
        
        return [repeated, missing]

public class Solution {
    public int[] FindMissingAndRepeatedValues(int[][] grid) {
        int n = grid.Length;
        Dictionary<int, int> count = new Dictionary<int, int>();
        
        // 统计每个数字出现的次数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int num = grid[i][j];
                if (count.ContainsKey(num)) {
                    count[num]++;
                } else {
                    count[num] = 1;
                }
            }
        }
        
        int repeated = -1, missing = -1;
        
        // 找出重复和缺失的数字
        for (int i = 1; i <= n * n; i++) {
            int freq = count.ContainsKey(i) ? count[i] : 0;
            if (freq == 2) {
                repeated = i;
            } else if (freq == 0) {
                missing = i;
            }
        }
        
        return new int[] { repeated, missing };
    }
}

var findMissingAndRepeatedValues = function(grid) {
    const n = grid.length;
    const count = new Array(n * n + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            count[grid[i][j]]++;
        }
    }
    
    let repeated = -1, missing = -1;
    for (let i = 1; i <= n * n; i++) {
        if (count[i] === 2) repeated = i;
        if (count[i] === 0) missing = i;
    }
    
    return [repeated, missing];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n²)
空间复杂度O(n²)

时间复杂度分析：

  • 遍历 n×n 矩阵需要 O(n²) 时间
  • 遍历 [1, n²] 范围查找重复和缺失数字需要 O(n²) 时间
  • 总时间复杂度为 O(n²)

空间复杂度分析：

  • 哈希表最多存储 n² 个不同的数字
  • 空间复杂度为 O(n²)