Toeplitz 매트릭스

난이도 쉽게
자주 묻는 질문 Facebook
배열 매트릭스조회수 92

2D가 주어지면 매트릭스 크기 (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 2
2 2
산출
그릇된
설명
Dialgonals는 [ "1", "2"], [ "2"], [ "2"]입니다.
대각선 [ "1", "2"]에는 다른 요소가 있으므로 행렬은 토플 리츠가 아닙니다.

Check Toeplitz Matrix를위한 알고리즘

모든 대각선을 하나씩 횡단하고 모든 요소가 대각선에 대해 동일하지 않으면 행렬은 Toeplitz가 아니며 그렇지 않으면 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

모든 대각선을 XNUMX 번째 행의 시작점.
대각선 1 : 시작점 = (0, 0)
요소 = {1, 1, 1}
모든 요소가 동일하므로 계속하십시오.
대각선 2 : 시작점 = (0, 1)
요소 = {2, 2, 2}
모든 요소가 동일하므로 계속하십시오.
대각선 3 : 시작점 = (0, 2)
요소 = {3, 3, 3}
모든 요소가 동일하므로 계속하십시오.
대각선 4 : 시작점 = (0, 3)
요소 = {4}
모든 요소가 동일하므로 계속하십시오.

모든 대각선을 XNUMX 번째 열의 시작점.
대각선 1 : 시작점 = (0, 0)
요소 = {1, 1, 1}
모든 요소가 동일하므로 계속하십시오.
대각선 2 : 시작점 = (1, 0)
요소 = {5, 5}
모든 요소가 동일하므로 계속하십시오.
대각선 3 : 시작점 = (2, 0)
요소 = {9}
모든 요소가 동일하므로 계속하십시오.

모든 대각선에는 동일한 요소가 있으므로 주어진 행렬은 Toeplitz입니다.

Toeplitz Matrix에 대한 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 (m * n)
공간 복잡성 = O (1) 
여기서 m과 n은 2D 행렬의 행과 열 수입니다.

참조

Translate »