题目地址:https://leetcode.com/problems/toeplitz-matrix/description/

题目描述

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素,那么这个矩阵是托普利茨矩阵。
给定一个 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]”上的元素不同。

说明:

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

进阶:

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

解题思路

最开始的思路想的有点复杂,把整个矩阵划成2*2的n个小矩阵,然后判断小矩阵左上和右下的对角线元素是否相等,如果每个小矩阵对角元素相等,那么合起来整个矩阵肯定是托普利茨矩阵,返回True

然后在划分n个小矩阵思路上想了半天。。

后来转变思路,用两层循环遍历矩阵中的元素,对于矩阵中的某个元素matrix[i][j], 判断该元素与matrix[i+1][j+1]是否相等,如果相等,则跳过,继续判断矩阵中的下一个元素;不相等直接返回Flase。当遍历完所有元素后,如果过程中没有False,则最后返回True。

在遍历矩阵元素的过程中,需要注意边界情况,比如对于矩阵$matrix = \begin{bmatrix}
1 & 2 & 3 & 4 \
5 & 1 & 2 & 3 \
9 & 5 & 1 & 2 \
\end{bmatrix}$, 4的右边没有列,9的下边没有行,所以对于3行4列的矩阵,只需要判断到第2行,第3列即可,不遍历最后一行和最后一列。

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def isToeplitzMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: bool
"""
if len(matrix)==1:
return True
for i in range(len(matrix)-1):
for j in range(len(matrix[i])-1):
if matrix[i][j] == matrix[i+1][j+1]:
continue
else:
return False
return True

Runtime: 56 ms

思路优化

上面的思路需要使用两层for循环遍历矩阵中的元素,时间复杂度会较高,可以思考进一步优化使用一层for循环。通过观察托普利茨矩阵matrix的每行元素,如下:

matrix矩阵第一行的第1到3个元素与第二行的第2到4个元素: $matrix = \begin{bmatrix}
\color{red}{1} & \color{red}{2} & \color{red}{3} & 4 \
5 & \color{red}{1} & \color{red}{2} & \color{red}{3} \
9 & 5 & 1 & 2 \
\end{bmatrix}$
matrix矩阵第二行的第1到3个元素与第三行的第2到4个元素: $matrix = \begin{bmatrix}
1 & 2 & 3 & 4 \
\color{red}{5} & \color{red}{1} & \color{red}{2} & 3 \
9 & \color{red}{5} & \color{red}{1} & \color{red}{2} \
\end{bmatrix}$

对于一个$M×N$的托普利茨矩阵,可以发现它满足第M行的第1~n-1元素与第M+1行的第2~n元素是相等的。因此,可以把一个一个元素判断的方法改进为一行一行的判断。

优化后代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def isToeplitzMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: bool
"""
if not matrix:
return False
colSize = len(matrix[0]) - 1
for row in range(len(matrix) - 1):
if matrix[row][:colSize] != matrix[row+1][1:colSize+1]:
return False
return True