1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
for (int rowStart = m - 1; rowStart >= 0; rowStart--) {
int currRow = rowStart, currCol = 0, diagVal = matrix[currRow][currCol];
while (currRow < m && currCol < n && matrix[currRow][currCol] == diagVal) {
currRow += 1;
currCol += 1;
}
if (currRow < m && currCol < n) {
return false;
}
}
for (int colStart = 1; colStart < n; colStart++) {
int currRow = 0, currCol = colStart, diagVal = matrix[currRow][currCol];
while (currRow < m && currCol < n && matrix[currRow][currCol] == diagVal) {
currRow += 1;
currCol += 1;
}
if (currRow < m && currCol < n) {
return false;
}
}
return true;
}
}
|
我的很naive的解法. 就是把每个对角线都遍历.
时间复杂度: O(m * n)
空间复杂度: O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][j] != matrix[i - 1][j - 1]) {
return false;
}
}
}
return true;
}
}
|
其他大神的做法. 就是遍历所有元素, 和自己的左上角比较即可. 对于row或者col是0的元素, 它们没有左上角, 因此直接跳过它们.
时间复杂度和空间复杂度不变.
