找出缺失和重复的数字

难度: Easy

给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [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 * 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 。

Submission

运行时间: 28 ms

内存: 16.7 MB

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        cnt = [0] * (n * n + 1)
        for row in grid:
            for x in row:
                cnt[x] += 1

        ans = [0, 0]
        for i in range(1, n * n + 1):
            if cnt[i] == 2:
                ans[0] = i
            elif cnt[i] == 0:
                ans[1] = i
        return ans

Explain

本题的思路是使用计数排序的思想。首先，创建一个长度为 n*n + 1 的计数数组 cnt，初始化所有元素为 0。然后，遍历二维矩阵 grid，对于矩阵中的每个元素 x，将 cnt[x] 的值加 1。这样，计数数组 cnt 中的每个元素的值就代表了对应数字在矩阵中出现的次数。接着，遍历计数数组 cnt，找到出现两次的数字和没有出现的数字，分别作为答案数组 ans 的第一个和第二个元素。最后，返回答案数组 ans。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        cnt = [0] * (n * n + 1)  # 创建计数数组
        for row in grid:
            for x in row:
                cnt[x] += 1  # 更新计数数组

        ans = [0, 0]
        for i in range(1, n * n + 1):
            if cnt[i] == 2:
                ans[0] = i  # 找到重复的数字
            elif cnt[i] == 0:
                ans[1] = i  # 找到缺失的数字
        return ans  # 返回答案数组

Explore

在题解中，计数数组 cnt 的大小为 n*n + 1 是为了确保能够覆盖从 1 到 n*n 的所有可能的数字。由于数组的索引是从 0 开始的，而数字是从 1 开始的，所以需要 n*n + 1 个元素来确保可以使用数字本身作为索引，避免索引溢出。这样，数组的最后一个索引 n*n 就可以正确表示数字 n*n。

题解中使用的计数排序思想通过遍历矩阵来逐一增加计数数组 cnt 中对应元素的值。这种方法能够准确记录每个数字在矩阵中出现的次数。只要矩阵的大小和数字范围是正确的，即每个数字理论上应该出现一次，那么通过检查 cnt 数组中的值，可以准确地找到出现两次的数字（重复）和未出现的数字（缺失）。理论上，只要输入数据符合预期的格式和范围，计数错误的可能性非常低。

是的，初始化计数数组 cnt 的每个元素为0确实意味着在开始时，每一个数字都被假设为缺失，因为它们的初始计数是0。随着矩阵的遍历和相应数字计数的增加，只有那些未在矩阵中出现过的数字会在 cnt 数组中保持为0，从而被识别为缺失。这种方法自然而然地处理了数字缺失的情况。

题解中的方法在当前形式下只能找到一个重复的数字和一个缺失的数字。如果存在多个重复或缺失的数字，这种方法还需要进行扩展。具体来说，可以通过创建两个列表，一个用于存储所有重复的数字，另一个用于存储所有缺失的数字。然后修改循环中的条件，将找到的每个重复和缺失的数字分别添加到对应的列表中。这样，方法就可以正确处理存在多个重复或缺失数字的情况。