766. Toeplitz Matrix

题目

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.

大意就是说如果一个矩阵的每个斜着对角线上的数都相同的话，这个矩阵是Toeplitz矩阵。

思路

1. 判断num[i][j]和num[i+1][j+1]是否相同。
2. 两个点在同一条对角线上满足r1-c1==r2-c2，所以将r-c作为key，matrix[r][c]作为value存入一个map，如果有一个matrix[r][c]不满足key对应的value，则返回false。

时间复杂度都是O(mn)，第一种方法的空间复杂度是O(1)，第二种是O(mn).

代码

bool isToeplitzMatrix(vector<vector<int>>& matrix) {
    
    int row=matrix.size(); int col=matrix[0].size();
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            if(i+1<row && j+1<col )
            {
               if(matrix[i][j]!=matrix[i+1][j+1]) return false;
            }
                
        }
    }
    return true;
}