What is the time complexity of the solution for Find Missing and Repeated Values?

The time complexity of the solution is O(n^2) because the grid needs to be scanned fully, and each element is processed once.

How do I approach solving Find Missing and Repeated Values using hash lookup?

You can use a hash table to store the frequency of each number and find which number repeats and which is missing by checking for the absence of a number in the hash table.

What is the role of mathematical sums in solving this problem?

Mathematical sums help by comparing the expected sum of numbers with the actual sum, providing a way to identify the missing and repeated numbers based on these differences.

How can I optimize space complexity for Find Missing and Repeated Values?

Space complexity can be optimized to O(1) by modifying the input grid directly, marking the visited numbers in place, instead of using an additional hash table.

What are the key pitfalls to avoid when solving Find Missing and Repeated Values?

Common pitfalls include using unnecessary extra space, not accounting for the exact number of repetitions, and mishandling edge cases such as the smallest possible grid.

#2965

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找出缺失和重复的数字

给你一个下标从 0 开始的二维整数矩阵 grid ，大小为 n * n ，其中的值在 [1, n 2 ] 范围内。除了 a 出现两次， b 缺失之外，每个整数都恰好出现一次。任务是找出重复的数字 a 和缺失的数字 b 。返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 …

数组哈希表数学矩阵

题目描述

给你一个下标从 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 。

lightbulb

解题思路

方法一：计数

我们创建一个长度为 $n^2 + 1$ 的数组 $cnt$ ，统计矩阵中每个数字出现的次数。

接下来遍历 $i \in [1, n^2]$ ，如果 $cnt[i] = 2$ ，则 $i$ 是重复的数字，我们将答案的第一个元素设为 $i$ ；如果 $cnt[i] = 0$ ，则 $i$ 是缺失的数字，我们将答案的第二个元素设为 $i$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是矩阵的边长。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        cnt = [0] * (n * n + 1)
        for row in grid:
            for v in row:
                cnt[v] += 1
        ans = [0] * 2
        for i in range(1, n * n + 1):
            if cnt[i] == 2:
                ans[0] = i
            if cnt[i] == 0:
                ans[1] = i
        return ans

speed

复杂度分析

指标	值
时间	O(n^2)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Efficiently applies array scanning combined with hash lookup for problem-solving.
question_mark
Handles edge cases such as the smallest grid and missing number properly.
question_mark
Uses mathematical tricks for sum or square comparisons in a clever manner.

warning

常见陷阱

外企场景

error
Not using an efficient hash table approach or array scanning pattern.
error
Missing the condition that exactly one number repeats, which can confuse the detection logic.
error
Overcomplicating the solution by introducing unnecessary algorithms or extra space usage.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling different grid sizes and ensuring the algorithm scales well.
arrow_right_alt
Applying the method to non-square grids or matrices.
arrow_right_alt
Exploring alternative methods that don’t involve hashing, such as sorting or indexing.

help

常见问题

外企场景

继续练习

#3044 出现频率最高的质数 #2963 统计好分割方案的数目 #2946 循环移位后的矩阵相似检查