Easy

题目描述

一个 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].length
  • 1 <= n <= 100
  • 1 <= matrix[i][j] <= n

解题思路

解题思路

这道题要求检查一个 n×n 矩阵是否有效，即每行和每列都包含 1 到 n 的所有数字。

有两种主要解法：

方法一：集合验证（推荐）

对于每一行和每一列，使用集合记录出现的数字。如果集合大小等于 n，说明包含了所有 1 到 n 的数字。这种方法简洁直观，时间复杂度为 O(n²)。

方法二：布尔数组标记

对每行每列使用布尔数组标记数字是否出现过，最后检查是否所有位置都被标记。虽然空间复杂度稍高，但逻辑清晰。

由于题目数据规模不大（n ≤ 100），两种方法都能很好地解决问题。这里推荐使用集合方法，因为代码更简洁，且 STL/标准库的集合实现经过高度优化。

具体实现时，我们遍历每一行，将行中元素加入集合，检查集合大小是否为 n；然后对每一列执行相同操作。任何一行或一列不满足条件就返回 false，全部通过则返回 true。

代码实现

class Solution {
public:
    bool checkValid(vector<vector<int>>& matrix) {
        int n = matrix.size();
        
        // 检查每一行
        for (int i = 0; i < n; i++) {
            unordered_set<int> rowSet;
            for (int j = 0; j < n; j++) {
                rowSet.insert(matrix[i][j]);
            }
            if (rowSet.size() != n) {
                return false;
            }
        }
        
        // 检查每一列
        for (int j = 0; j < n; j++) {
            unordered_set<int> colSet;
            for (int i = 0; i < n; i++) {
                colSet.insert(matrix[i][j]);
            }
            if (colSet.size() != n) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        
        # 检查每一行
        for i in range(n):
            row_set = set()
            for j in range(n):
                row_set.add(matrix[i][j])
            if len(row_set) != n:
                return False
        
        # 检查每一列
        for j in range(n):
            col_set = set()
            for i in range(n):
                col_set.add(matrix[i][j])
            if len(col_set) != n:
                return False
        
        return True

public class Solution {
    public bool CheckValid(int[][] matrix) {
        int n = matrix.Length;
        
        // 检查每一行
        for (int i = 0; i < n; i++) {
            HashSet<int> rowSet = new HashSet<int>();
            for (int j = 0; j < n; j++) {
                rowSet.Add(matrix[i][j]);
            }
            if (rowSet.Count != n) {
                return false;
            }
        }
        
        // 检查每一列
        for (int j = 0; j < n; j++) {
            HashSet<int> colSet = new HashSet<int>();
            for (int i = 0; i < n; i++) {
                colSet.Add(matrix[i][j]);
            }
            if (colSet.Count != n) {
                return false;
            }
        }
        
        return true;
    }
}

var checkValid = function(matrix) {
    const n = matrix.length;
    
    // 检查每一行
    for (let i = 0; i < n; i++) {
        const rowSet = new Set();
        for (let j = 0; j < n; j++) {
            rowSet.add(matrix[i][j]);
        }
        if (rowSet.size !== n) {
            return false;
        }
    }
    
    // 检查每一列
    for (let j = 0; j < n; j++) {
        const colSet = new Set();
        for (let i = 0; i < n; i++) {
            colSet.add(matrix[i][j]);
        }
        if (colSet.size !== n) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)需要遍历矩阵的每个元素两次（行检查和列检查）
空间复杂度O(n)使用集合存储每行/每列的元素，最多存储 n 个元素

相关题目