LeetCode 题解工作台
检查是否每一行每一列都包含全部整数
对一个大小为 n x n 的矩阵而言，如果其每一行和每一列都包含从 1 到 n 的 全部 整数（含 1 和 n ），则认为该矩阵是一个 有效 矩阵。 给你一个大小为 n x n 的整数矩阵 matrix ，请你判断矩阵是否为一个有效矩阵：如果是，返回 true ；否则，返回 false 。 示例 1…
3
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
遍历矩阵的每一行和每一列，使用哈希表记录每个数字是否出现过，如果某一行或某一列中有数字重复出现，则返回 `false`，否则返回 `true`。 时间复杂度 ，空间复杂度 。其中 为矩阵的大小。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
对一个大小为 n x n 的矩阵而言，如果其每一行和每一列都包含从 1 到 n 的 全部 整数（含 1 和 n），则认为该矩阵是一个 有效 矩阵。
给你一个大小为 n x n 的整数矩阵 matrix ，请你判断矩阵是否为一个有效矩阵：如果是，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,2,3],[3,1,2],[2,3,1]] 输出：true 解释：在此例中，n = 3 ，每一行和每一列都包含数字 1、2、3 。 因此，返回 true 。
示例 2：
输入：matrix = [[1,1,1],[1,2,3],[1,2,3]] 输出：false 解释：在此例中，n = 3 ，但第一行和第一列不包含数字 2 和 3 。 因此，返回 false 。
提示：
n == matrix.length == matrix[i].length1 <= n <= 1001 <= matrix[i][j] <= n
解题思路
方法一：哈希表
遍历矩阵的每一行和每一列，使用哈希表记录每个数字是否出现过，如果某一行或某一列中有数字重复出现，则返回 false，否则返回 true。
时间复杂度 ，空间复杂度 。其中 为矩阵的大小。
class Solution:
def checkValid(self, matrix: List[List[int]]) -> bool:
n = len(matrix)
return all(len(set(row)) == n for row in chain(matrix, zip(*matrix)))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) because each of the n rows and n columns is scanned once. Space complexity is O(n) for the hash set used per row or column check. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate efficiently uses a hash set for duplicate detection per row and column.
- question_mark
Observe whether they correctly iterate over both rows and columns without missing edge cases.
- question_mark
Listen for explanations about why this pattern avoids scanning the entire matrix multiple times unnecessarily.
常见陷阱
外企场景- error
Failing to check both rows and columns can produce incorrect results even if rows are valid.
- error
Using a single hash set for the entire matrix instead of per row/column can cause false positives.
- error
Ignoring numbers outside the 1 to n range violates the problem constraints.
进阶变体
外企场景- arrow_right_alt
Check if the matrix is Latin square where numbers may start from 0 instead of 1.
- arrow_right_alt
Determine if only rows or only columns need to contain all numbers from 1 to n.
- arrow_right_alt
Validate larger sparse matrices efficiently using bit masks instead of hash sets.