LeetCode766. 托普利茨矩阵

爱被打了一巴掌 2022-05-19 07:57 126阅读 0赞

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是*托普利茨矩阵*。

给定一个 `M x N` 的矩阵，当且仅当它是*托普利茨矩阵*时返回 `True`。

**示例 1:**

输入: 
    matrix = [
      [1,2,3,4],
      [5,1,2,3],
      [9,5,1,2]
    ]
    输出: True
    解释:
    在上述矩阵中, 其对角线为:
    "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。
    各条对角线上的所有元素均相同, 因此答案是True。

**示例 2:**

输入:
    matrix = [
      [1,2],
      [2,2]
    ]
    输出: False
    解释: 
    对角线"[1, 2]"上的元素不同。

**说明:**

1.  `matrix` 是一个包含整数的二维数组。
2.  `matrix` 的行数和列数均在 `[1, 20]`范围内。
3.  `matrix[i][j]` 包含的整数在 `[0, 99]`范围内。

**进阶:**

1.  如果矩阵存储在磁盘上，并且磁盘内存是有限的，因此一次最多只能将一行矩阵加载到内存中，该怎么办？
2.  如果矩阵太大以至于只能一次将部分行加载到内存中，该怎么办？

--------------------

思路：借助set结构来判断每条对角线的所有元素是否相同。找对角线的元素方法为行，列索引分别加一。

eg. a\[0\]\[0\] >>a\[1\]\[1\]>>a\[2\[2\]

a\[0\]\[1\]>>a\[1\]\[2\]>>a\[2\]\[3\]

class Solution {
        public boolean isToeplitzMatrix(int[][] matrix) {
            Set<Integer> set=new HashSet<Integer>();
            int m=matrix.length;   //行
            int n=matrix[0].length;//列
            
            for(int i=0;i<m;i++) {
            	set.clear();
            	for(int s=i,t=0;s<m&&t<n;s++,t++) {
            //		System.out.print(matrix[s][t]+" ");
            		set.add(matrix[s][t]);
            		if(set.size()>1) {
            			return false;
            		}
            	}
            //	System.out.println();
            }
            
            for(int i=0;i<n;i++) {
            	set.clear();
            	for(int s=0,t=i;s<m&&t<n;s++,t++) {
            //		System.out.print(matrix[s][t]+" ");
            		set.add(matrix[s][t]);
            		if(set.size()>1) {
            			return false;
            		}
            	}
           // 	System.out.println();
            }
    	   return true;
        }
    }