托普利茲矩陣


難度級別 容易獎學金
經常問 Facebook
排列 矩陣

給定二維 矩陣 大小(mxn),請檢查矩陣是否為Toeplitz。 Toeplitz矩陣是這樣一個矩陣,其中從所有左上角到左上角到左下角在同一對角線上的元素都是相同的。

範例檔案

輸入
1 2 3 4
5 1 2 3
9 5 1 2
產量

解釋
對角線是[“ 1”,“ 1”,“ 1”],[“ 2”,“ 2”,“ 2”],[“ 3”,“ 3”],[“ 4”],[“ 5 ”,“ 5”],[“ 9”]
在每個對角線上,所有元素都相同,因此矩陣為Toeplitz。

輸入
1 2th Street, Suite XNUMX
2 2th Street, Suite XNUMX
產量

解釋
方言是[“ 1”,“ 2”],[“ 2”],[“ 2”]
對角線[“ 1”,“ 2”]具有不同的元素,因此矩陣不成正立。

檢查托普利茲矩陣的算法

遍歷所有對角線,如果所有元素對一個對角線都不相同,則矩陣不是Toeplitz,否則為Toeplitz。
對角線的移動如下圖所示,

托普利茲矩陣

在上述示例中,對角線的起點是[0,0],[0,1],[0,2],[0,3],[1,0],[2,0]。
起點處的列或行為0,從起點開始並通過將行和列的值增加1來遍歷每個對角線。

Toeplitz矩陣的說明

考慮這個例子,
1 2 3 4
5 1 2 3
9 5 1 2

遍歷所有對角線 第零行的起點.
對角線1 :起點=(0,0)
元素= {1,1,1}
所有元素都相同,因此繼續。
對角線2 :起點=(0,1)
元素= {2,2,2}
所有元素都相同,因此繼續。
對角線3 :起點=(0,2)
元素= {3,3,3}
所有元素都相同,因此繼續。
對角線4 :起點=(0,3)
元素= {4}
所有元素都相同,因此繼續。

遍歷所有對角線 第零列的起點。
對角線1 :起點=(0,0)
元素= {1,1,1}
所有元素都相同,因此繼續。
對角線2 :起點=(1,0)
元素= {5,5}
所有元素都相同,因此繼續。
對角線3 :起點=(2,0)
元素= {9}
所有元素都相同,因此繼續。

所有對角線都有相同的元素,因此給定的矩陣為Toeplitz。

Toeplitz矩陣的JAVA代碼

public class ToeplitzMatrix {
    private static boolean isToeplitz(int[][] matrix) {
        boolean ans = true;
        int n = matrix.length;
        int m = matrix[0].length;
        
        // First row diagonals
        for (int i = 0; i < m; i++) {
            int x = 0, y = i;
            int curr = matrix[x][y];
            x++; y++;
            while (x < n && y < m) {
                // If any element is not same, this can't be a toeplitz matrix
                if (matrix[x][y] != curr) {
                    ans = false;
                    break;
                }
                // Increment row and column by 1
                x++; y++;
            }
            if (!ans)
                break;
        }

        // First column diagonals
        for (int i = 1; i < n; i++) {
            int x = i, y = 0;
            int curr = matrix[x][y];
            x++; y++;
            while (x < n && y < m) {
                // If any element is not same, this can't be a toeplitz matrix
                if (matrix[x][y] != curr) {
                    ans = false;
                    break;
                }
                // Increment row and column by 1
                x++; y++;
            }
            if (!ans)
                break;
        }

        return ans;
    }

    public static void main(String[] args) {
        // Example 1
        int[][] matrix = new int[][] {
                {1, 2, 3, 4},
                {5, 1, 2, 3},
                {9, 5, 1, 2}};
        System.out.println(isToeplitz(matrix));

        // Example 2
        int[][] matrix2 = new int[][] {
                {1, 2},
                {2, 2}
        };
        System.out.println(isToeplitz(matrix2));
    }
}

Toeplitz矩陣的C ++代碼

#include<bits/stdc++.h> 
using namespace std;

int matrix[4][4];

bool isToeplitz(int n, int m) {
    bool ans = true;

    // First row diagonals
    for (int i = 0; i < m; i++) {
        int x = 0, y = i;
        int curr = matrix[x][y];
        x++; y++;
        while (x < n && y < m) {
            // If any element is not same, this can't be a toeplitz matrix
            if (matrix[x][y] != curr) {
                ans = false;
                break;
            }
            // Increment row and column by 1
            x++; y++;
        }
        if (!ans)
            break;
    }

    // First column diagonals
    for (int i = 1; i < n; i++) {
        int x = i, y = 0;
        int curr = matrix[x][y];
        x++; y++;
        while (x < n && y < m) {
            // If any element is not same, this can't be a toeplitz matrix
            if (matrix[x][y] != curr) {
                ans = false;
                break;
            }
            // Increment row and column by 1
            x++; y++;
        }
        if (!ans)
            break;
    }

    return ans;
}

int main() {
    // Example 1
    matrix[0][0] = 1;
    matrix[0][1] = 2;
    matrix[0][2] = 3;
    matrix[0][3] = 4;
    matrix[1][0] = 5;
    matrix[1][1] = 1;
    matrix[1][2] = 2;
    matrix[1][3] = 3;
    matrix[2][0] = 9;
    matrix[2][1] = 5;
    matrix[2][2] = 1;
    matrix[2][3] = 2;
    if (isToeplitz(3, 4)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    matrix[0][0] = 1;
    matrix[0][1] = 2;
    matrix[1][0] = 2;
    matrix[1][1] = 2;
    if (isToeplitz(2, 2)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

複雜度分析

時間複雜度= O(米* n)
空間複雜度= O(1) 
其中m和n是2D矩陣中的行數和列數。

參考