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
Solution: Bitset / hashtable
Time complexity: O(n2)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: bool checkValid(vector<vector<int>>& matrix) { const int n = matrix.size(); for (int i = 0; i < n; ++i) { bitset<101> row; bitset<101> col; for (int j = 0; j < n; ++j) col[matrix[i][j]] = row[matrix[j][i]] = true; if (row.count() != n || col.count() != n) return false; } return true; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment