[LeetCode] 2133. Check if Every Row and Column Contains All Numbers

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 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/check-if-every-row-and-column-contains-all-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题跟 Sudoku 几乎一样，但是简单一些，只需要检查同一行和同一列。这里我创建两个二维数组来记录每一行和每一列是否有重复元素。

复杂度

时间O(n^2)
空间O(n^2)

代码

Java实现

class Solution {
    public boolean checkValid(int[][] matrix) {
        int n = matrix.length;
        boolean[][] rows = new boolean[n][n];
        boolean[][] cols = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int num = matrix[i][j];
                if (rows[i][num - 1] || cols[num - 1][j]) {
                    return false;
                } else {
                    rows[i][num - 1] = true;
                    cols[num - 1][j] = true;
                }
            }
        }
        return true;
    }
}

相关题目

36. Valid Sudoku
37. Sudoku Solver
2133. Check if Every Row and Column Contains All Numbers