1042. Toeplitz Matrix

Posted on

每天做两题算法题净化心灵

  1. Toeplitz Matri

Description

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: True
Explanation:
1234
5123
9512

In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and 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.

Solution 1

最直观，两个for完事，O(n^m)的时间复杂度

Solution 2

实际上一个循环也是可以的，把矩阵看成是一个序列。
当前的i索引目标和下一行的i+1索引目标必须相当，如果索引是每一行的最后一个的话就不用管了，再有就是最后一行也不需要去判断了。
时间复杂度 < O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param matrix: the given matrix
 * @return: True if and only if the matrix is Toeplitz
 */
const isToeplitzMatrix = function (matrix) {
    var len = matrix[0].length;
    var rows = matrix.length;
    if (len == 1) return true;

    var i = 0;
    while (i < (len * rows - len)){
        if (i % len !== (len-1)){
            if ((matrix[Math.floor(i/len)][i%len]) !== matrix[Math.floor((i + len + 1)/len)][(i + len + 1)%len])
                return false;
        }
        i++;
    }
    
    return true;
}