A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1:

Input:
matrix = [
[1,2,3,4],
[5,1,2,3],
[9,5,1,2]
]
Output: True
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

Example 2:

Input:
matrix = [
[1,2],
[2,2]
]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.

Note:

  1. matrix will be a 2D array of integers.
  2. matrix will have a number of rows and columns in range [1, 20].
  3. matrix[i][j] will be integers in range [0, 99].

Follow up:
  1. What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
  2. What if the matrix is so large that you can only load up a partial row into the memory at once?

题意：

给你一个M×N的矩阵matrix，让判断这个矩阵是否为Toeplitz矩阵（托普利兹矩阵），所谓的托普利兹矩阵就是说：除了第一行和第一列外其他元素都与左上角的元素相等（我的程序就是用这个思想实现的）。如果是Toeplitz矩阵就返回true，否则返回false。

以下为代码：

class Solution {
public:
bool isToeplitzMatrix(vector<vector<int>>& matrix) {
int rows=matrix.size();
int cols=matrix[0].size();
if(rows+cols<=2)
return true;
// if(rows<2 || cols<2) // Note中都说是2D的了，没想到LeetCode上还有一个元素来测试的，最后改成上面的if判断
// return false;
bool res=true;
for(int r=0;r<rows-1;r++)
{
for(int c=0;c<cols-1;c++)
{
if(matrix[r][c]!=matrix[r+1][c+1])
res=false;
}
}
return res;

}
};

对于题中提到的Follow up，我想到的是将外层循环换成每次读取一行内容来判断，不知道矩阵大的话时间效率怎么样。

推荐阅读：

相关文章