2133. 检查是否每一行每一列都包含全部整数

🟢   🔖  数组 哈希表 矩阵  🔗 力扣 LeetCode

题目

An n x n matrix is valid if every row and every column contains all the integers from 1 to n (inclusive).

Given an n x n integer matrix matrix, return true if the matrix is valid. Otherwise, return false.

Example 1:

Input: matrix = [[1,2,3],[3,1,2],[2,3,1]]

Output: true

Explanation: In this case, n = 3, and every row and column contains the numbers 1, 2, and 3.

Hence, we return true.

Example 2:

Input: matrix = [[1,1,1],[1,2,3],[1,2,3]]

Output: false

Explanation: In this case, n = 3, but the first row and the first column do not contain the numbers 2 or 3.

Hence, we return false.

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• 1 <= matrix[i][j] <= n

题目大意

对一个大小为 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

解题思路

1. 遍历行与列：

   • 对每一行和每一列分别建立集合。
   • 使用集合的特性（自动去重），如果集合的大小小于 n，说明存在重复或缺少的数字。

2. 判断条件：

   • 如果任意行或任意列的集合大小小于 n，直接返回 false。
   • 如果所有行和列都符合条件，则返回 true。

3. 提前终止：

   • 为提高效率，一旦发现某一行或列不满足条件，可以直接终止后续的判断。

复杂度分析

• 时间复杂度：O(n^2)，两层循环，检查矩阵中的每个元素。
• 空间复杂度：O(n)，使用集合存储行和列的元素。

代码

/**
 * @param {number[][]} matrix
 * @return {boolean}
 */
var checkValid = function (matrix) {
	const n = matrix.length; // 矩阵的大小 n x n
	for (let i = 0; i < n; i++) {
		// 初始化行和列的集合
		let row = new Set(matrix[i]); // 第 i 行
		let col = new Set(); // 第 i 列

		for (let j = 0; j < n; j++) {
			col.add(matrix[j][i]); // 收集第 i 列的元素
		}

		// 检查行和列是否都包含 n 个元素
		if (row.size < n || col.size < n) return false;
	}
	return true; // 所有行和列都满足条件
};

相关题目

题号	标题	题解	标签	难度	力扣
36	有效的数独	[✓]	数组 哈希表 矩阵	🟠	🀄️ 🔗
1572	矩阵对角线元素的和	[✓]	数组 矩阵	🟢	🀄️ 🔗
2661	找出叠涂元素		数组 哈希表 矩阵	🟠	🀄️ 🔗