Descubra se determinada matriz é Toeplitz ou não
Dada uma matriz quadrada juntamente com[][] de ordem n sua tarefa é verificar se é uma matriz Toeplitz.
Observação: Uma matriz Toeplitz - também chamada de matriz constante diagonal - é uma matriz onde os elementos de cada diagonal descendente individual são iguais da esquerda para a direita. Equivalentemente, para qualquer entrada mat[i][j] é o mesmo que mat[i-1][j-1] ou mat[i-2][j-2] e assim por diante.
Exemplos:
Entrada: com[][] = [ [6 7 8]
[4 6 7]
[146]]
Saída: Sim
Explicação: Todas as diagonais da matriz dada são [6 6 6] [7 7] [8] [4 4] [1]. Para cada diagonal, como todos os elementos são iguais, a matriz fornecida é a Matriz Toeplitz.Entrada: com[][] = [ [6 3 8]
[4 9 7]
[146]]
Saída: Não
Explicação: Os elementos diagonais primários da matriz dada são [6 9 6]. Como os elementos diagonais não são iguais, a matriz fornecida não é a Matriz Toeplitz.
[Abordagem esperada - 1] - Verificando cada diagonal - O(n * n) Tempo e O(1) Espaço
A ideia é percorrer cada diagonal inclinada para baixo na matriz usando cada elemento na primeira linha e cada elemento na primeira coluna como ponto de partida e verificar se cada elemento ao longo dessa diagonal corresponde ao valor em sua cabeça.
Siga as etapas abaixo:
- Deixar
n = mat.size()em = mat[0].size(). - Para cada índice de coluna
ide0param - 1chamarcheckDiagonal(mat 0 i); se retornar falso retorne imediatamente falso deisToeplitz. - Para cada índice de linha
ide0paran - 1chamarcheckDiagonal(mat i 0); se retornar falso retorne imediatamente falso deisToeplitz. - Se todas as chamadas para
checkDiagonalsucesso retornar verdadeiro. - Em
checkDiagonal(mat x y)compararmat[i][j]paramat[x][y]para cadai = x+1 j = y+1enquantoi < n && j < m; retorne falso na primeira incompatibilidade, caso contrário, retorne verdadeiro após atingir o limite.
Abaixo é dado o implementação:
C++ #include using namespace std ; // function to check if diagonal elements are same bool checkDiagonal ( vector < vector < int >> & mat int x int y ) { int n = mat . size () m = mat [ 0 ]. size (); for ( int i = x + 1 j = y + 1 ; i < n && j < m ; i ++ j ++ ) { if ( mat [ i ][ j ] != mat [ x ][ y ]) return false ; } return true ; } // Function to check whether given // matrix is toeplitz matrix or not bool isToeplitz ( vector < vector < int >> & mat ) { int n = mat . size () m = mat [ 0 ]. size (); // check each descending diagonal starting from // first row and first column of the matrix for ( int i = 0 ; i < m ; i ++ ) if ( ! checkDiagonal ( mat 0 i )) return false ; for ( int i = 0 ; i < n ; i ++ ) if ( ! checkDiagonal ( mat i 0 )) return false ; // if all diagonals are same return true return true ; } int main () { vector < vector < int >> mat = { { 6 7 8 } { 4 6 7 } { 1 4 6 } }; if ( isToeplitz ( mat )) { cout < < 'Yes' ; } else { cout < < 'No' ; } return 0 ; }
Java import java.util.* ; class GfG { // function to check if diagonal elements are same static boolean checkDiagonal ( List < List < Integer >> mat int x int y ) { int n = mat . size () m = mat . get ( 0 ). size (); for ( int i = x + 1 j = y + 1 ; i < n && j < m ; i ++ j ++ ) { if ( ! mat . get ( i ). get ( j ). equals ( mat . get ( x ). get ( y ))) return false ; } return true ; } // Function to check whether given // matrix is toeplitz matrix or not static boolean isToeplitz ( List < List < Integer >> mat ) { int n = mat . size () m = mat . get ( 0 ). size (); // check each descending diagonal starting from // first row and first column of the matrix for ( int i = 0 ; i < m ; i ++ ) if ( ! checkDiagonal ( mat 0 i )) return false ; for ( int i = 0 ; i < n ; i ++ ) if ( ! checkDiagonal ( mat i 0 )) return false ; // if all diagonals are same return true return true ; } public static void main ( String [] args ) { List < List < Integer >> mat = Arrays . asList ( Arrays . asList ( 6 7 8 ) Arrays . asList ( 4 6 7 ) Arrays . asList ( 1 4 6 ) ); if ( isToeplitz ( mat )) { System . out . println ( 'Yes' ); } else { System . out . println ( 'No' ); } } }
Python # function to check if diagonal elements are same def checkDiagonal ( mat x y ): n m = len ( mat ) len ( mat [ 0 ]) i j = x + 1 y + 1 while i < n and j < m : if mat [ i ][ j ] != mat [ x ][ y ]: return False i += 1 j += 1 return True # Function to check whether given # matrix is toeplitz matrix or not def isToeplitz ( mat ): n m = len ( mat ) len ( mat [ 0 ]) # check each descending diagonal starting from # first row and first column of the matrix for i in range ( m ): if not checkDiagonal ( mat 0 i ): return False for i in range ( n ): if not checkDiagonal ( mat i 0 ): return False # if all diagonals are same return true return True mat = [ [ 6 7 8 ] [ 4 6 7 ] [ 1 4 6 ] ] if isToeplitz ( mat ): print ( 'Yes' ) else : print ( 'No' )
C# using System ; using System.Collections.Generic ; class GfG { // function to check if diagonal elements are same static bool checkDiagonal ( List < List < int >> mat int x int y ) { int n = mat . Count m = mat [ 0 ]. Count ; for ( int i = x + 1 j = y + 1 ; i < n && j < m ; i ++ j ++ ) { if ( mat [ i ][ j ] != mat [ x ][ y ]) return false ; } return true ; } // Function to check whether given // matrix is toeplitz matrix or not static bool isToeplitz ( List < List < int >> mat ) { int n = mat . Count m = mat [ 0 ]. Count ; // check each descending diagonal starting from // first row and first column of the matrix for ( int i = 0 ; i < m ; i ++ ) if ( ! checkDiagonal ( mat 0 i )) return false ; for ( int i = 0 ; i < n ; i ++ ) if ( ! checkDiagonal ( mat i 0 )) return false ; // if all diagonals are same return true return true ; } static void Main () { var mat = new List < List < int >> { new List < int > { 6 7 8 } new List < int > { 4 6 7 } new List < int > { 1 4 6 } }; if ( isToeplitz ( mat )) { Console . WriteLine ( 'Yes' ); } else { Console . WriteLine ( 'No' ); } } }
JavaScript // function to check if diagonal elements are same function checkDiagonal ( mat x y ) { let n = mat . length m = mat [ 0 ]. length ; for ( let i = x + 1 j = y + 1 ; i < n && j < m ; i ++ j ++ ) { if ( mat [ i ][ j ] !== mat [ x ][ y ]) return false ; } return true ; } // Function to check whether given // matrix is toeplitz matrix or not function isToeplitz ( mat ) { let n = mat . length m = mat [ 0 ]. length ; // check each descending diagonal starting from // first row and first column of the matrix for ( let i = 0 ; i < m ; i ++ ) if ( ! checkDiagonal ( mat 0 i )) return false ; for ( let i = 0 ; i < n ; i ++ ) if ( ! checkDiagonal ( mat i 0 )) return false ; // if all diagonals are same return true return true ; } let mat = [ [ 6 7 8 ] [ 4 6 7 ] [ 1 4 6 ] ]; if ( isToeplitz ( mat )) { console . log ( 'Yes' ); } else { console . log ( 'No' ); }
Saída
Yes
[Abordagem esperada - 2] - Verificando diagonalmente acima do elemento - O(n * n) Tempo e O(1) Espaço
A ideia é varrer cada célula da segunda linha e da segunda coluna em diante, comparando cada valor com seu vizinho superior esquerdo. Se algum elemento for diferente daquele que está diagonalmente acima dele, você encontrou uma violação da propriedade Toeplitz e pode parar imediatamente; se você percorrer toda a matriz sem incompatibilidade, todas as diagonais serão constantes.
Siga as etapas abaixo:
- Deixar
n = mat.size()em = mat[0].size(). - Iterar
ide 1 an - 1e dentro dissojde 1 am - 1. - Se
mat[i][j] != mat[i - 1][j - 1]a qualquer momento retornarfalse. - Depois que todos os pares forem verificados sem incompatibilidades, retorne
true.
Abaixo é dado o implementação:
C++ #include using namespace std ; // Function to check whether given // matrix is toeplitz matrix or not bool isToeplitz ( vector < vector < int >> & mat ) { int n = mat . size () m = mat [ 0 ]. size (); // check diagonally above element of // each element in the matrix for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 1 ; j < m ; j ++ ) { if ( mat [ i ][ j ] != mat [ i - 1 ][ j - 1 ]) return false ; } } // if all diagonals are same return true return true ; } int main () { vector < vector < int >> mat = { { 6 7 8 } { 4 6 7 } { 1 4 6 } }; if ( isToeplitz ( mat )) { cout < < 'Yes' ; } else { cout < < 'No' ; } return 0 ; }
Java import java.util.* ; class GfG { // Function to check whether given // matrix is toeplitz matrix or not static boolean isToeplitz ( List < List < Integer >> mat ) { int n = mat . size () m = mat . get ( 0 ). size (); // check diagonally above element of // each element in the matrix for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 1 ; j < m ; j ++ ) { if ( mat . get ( i ). get ( j ) != mat . get ( i - 1 ). get ( j - 1 )) return false ; } } // if all diagonals are same return true return true ; } public static void main ( String [] args ) { List < List < Integer >> mat = Arrays . asList ( Arrays . asList ( 6 7 8 ) Arrays . asList ( 4 6 7 ) Arrays . asList ( 1 4 6 ) ); if ( isToeplitz ( mat )) { System . out . println ( 'Yes' ); } else { System . out . println ( 'No' ); } } }
Python # Function to check whether given # matrix is toeplitz matrix or not def isToeplitz ( mat ): n m = len ( mat ) len ( mat [ 0 ]) # check diagonally above element of # each element in the matrix for i in range ( 1 n ): for j in range ( 1 m ): if mat [ i ][ j ] != mat [ i - 1 ][ j - 1 ]: return False # if all diagonals are same return true return True mat = [ [ 6 7 8 ] [ 4 6 7 ] [ 1 4 6 ] ] if isToeplitz ( mat ): print ( 'Yes' ) else : print ( 'No' )
C# using System ; using System.Collections.Generic ; class GfG { // Function to check whether given // matrix is toeplitz matrix or not static bool isToeplitz ( List < List < int >> mat ) { int n = mat . Count m = mat [ 0 ]. Count ; // check diagonally above element of // each element in the matrix for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 1 ; j < m ; j ++ ) { if ( mat [ i ][ j ] != mat [ i - 1 ][ j - 1 ]) return false ; } } // if all diagonals are same return true return true ; } static void Main () { var mat = new List < List < int >> { new List < int > { 6 7 8 } new List < int > { 4 6 7 } new List < int > { 1 4 6 } }; if ( isToeplitz ( mat )) { Console . WriteLine ( 'Yes' ); } else { Console . WriteLine ( 'No' ); } } }
JavaScript // Function to check whether given // matrix is toeplitz matrix or not function isToeplitz ( mat ) { let n = mat . length m = mat [ 0 ]. length ; // check diagonally above element of // each element in the matrix for ( let i = 1 ; i < n ; i ++ ) { for ( let j = 1 ; j < m ; j ++ ) { if ( mat [ i ][ j ] !== mat [ i - 1 ][ j - 1 ]) return false ; } } // if all diagonals are same return true return true ; } let mat = [ [ 6 7 8 ] [ 4 6 7 ] [ 1 4 6 ] ]; if ( isToeplitz ( mat )) { console . log ( 'Yes' ); } else { console . log ( 'No' ); }
Saída
Yes
[Abordagem Alternativa] - Usando Hashing - O(n * n) Tempo e O(n) Espaço
A ideia é atribuir um identificador exclusivo a cada diagonal inferior direita (o índice da linha menos o índice da coluna) e usar um mapa hash para registrar o primeiro valor visto para aquela diagonal. Ao digitalizar toda a matriz, você calcula essa chave para cada célula e verifica se ela corresponde ao valor armazenado ou se é nova, armazena-a. Uma única incompatibilidade permite que você abandone o falso; caso contrário, você conclui verdadeiro no final.
Siga as etapas abaixo:
- Determine as dimensões da matriz (contagem de linhas e contagem de colunas) de
mat. - Crie um hashmap vazio
mppara mapear cada chave diagonal para seu valor representativo. - Percorra cada célula em
matpelo seu índice de linhaie índice de colunaj. - Para cada célula forme a chave diagonal subtraindo
jdei. - Se
mpjá contém esta chave compara o elemento atual com o valor armazenado; se forem diferentes, retorne falso imediatamente. - Se a chave ainda não estiver em
mpregistre o elemento atual sob essa chave. - Se você concluir a travessia sem nenhuma incompatibilidade, retorne verdadeiro.
Ilustração:
O diagrama abaixo dá uma melhor visualização dessa ideia. Considere a diagonal colorida em amarelo. A diferença entre o valor x e o valor y de qualquer índice nesta diagonal é 2 (2-0 3-1 4-2 5-3). O mesmo pode ser observado para todas as diagonais do corpo.
Para a cor vermelha a diferença diagonal é 3. Para a cor verde a diferença diagonal é 0. Para a cor laranja a diferença diagonal é -2 e assim por diante...
Abaixo é dado o implementação:
C++ #include using namespace std ; // Function to check whether given // matrix is toeplitz matrix or not bool isToeplitz ( vector < vector < int >> & mat ) { int n = mat . size () m = mat [ 0 ]. size (); // HashMap to store keyvalue pairs unordered_map < int int > mp ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { int key = i - j ; // If key value exists in the hashmap if ( mp [ key ]) { // check if the value is same // as the current element if ( mp [ key ] != mat [ i ][ j ]) return false ; } // Else we put keyvalue pair in hashmap else { mp [ i - j ] = mat [ i ][ j ]; } } } return true ; } int main () { vector < vector < int >> mat = { { 6 7 8 } { 4 6 7 } { 1 4 6 } }; if ( isToeplitz ( mat )) { cout < < 'Yes' ; } else { cout < < 'No' ; } return 0 ; }
Java // JAVA program to check whether given matrix // is a Toeplitz matrix or not import java.util.* ; class GFG { static boolean isToeplitz ( int [][] matrix ) { // row = number of rows // col = number of columns int row = matrix . length ; int col = matrix [ 0 ] . length ; // HashMap to store keyvalue pairs HashMap < Integer Integer > map = new HashMap < Integer Integer > (); for ( int i = 0 ; i < row ; i ++ ) { for ( int j = 0 ; j < col ; j ++ ) { int key = i - j ; // if key value exists in the hashmap if ( map . containsKey ( key )) { // we check whether the current value // stored in this key matches to element // at current index or not. If not // return false if ( map . get ( key ) != matrix [ i ][ j ] ) return false ; } // else we put keyvalue pair in hashmap else { map . put ( i - j matrix [ i ][ j ] ); } } } return true ; } // Driver Code public static void main ( String [] args ) { int [][] matrix = { { 12 23 - 32 } { - 20 12 23 } { 56 - 20 12 } { 38 56 - 20 } }; // Function call String result = ( isToeplitz ( matrix )) ? 'Yes' : 'No' ; System . out . println ( result ); } }
Python # Python3 program to check whether given matrix # is a Toeplitz matrix or not def isToeplitz ( matrix ): # row = number of rows # col = number of columns row = len ( matrix ) col = len ( matrix [ 0 ]) # dictionary to store keyvalue pairs map = {} for i in range ( row ): for j in range ( col ): key = i - j # if key value exists in the map if ( key in map ): # we check whether the current value stored # in this key matches to element at current # index or not. If not return false if ( map [ key ] != matrix [ i ][ j ]): return False # else we put keyvalue pair in map else : map [ key ] = matrix [ i ][ j ] return True # Driver Code if __name__ == '__main__' : matrix = [[ 12 23 - 32 ] [ - 20 12 23 ] [ 56 - 20 12 ] [ 38 56 - 20 ]] # Function call if ( isToeplitz ( matrix )): print ( 'Yes' ) else : print ( 'No' )
C# using System ; using System.Collections.Generic ; class GfG { // Function to check whether given // matrix is toeplitz matrix or not static bool isToeplitz ( List < List < int >> mat ) { int n = mat . Count m = mat [ 0 ]. Count ; // HashMap to store keyvalue pairs Dictionary < int int > mp = new Dictionary < int int > (); for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { int key = i - j ; // If key value exists in the hashmap if ( mp . ContainsKey ( key )) { // check if the value is same // as the current element if ( mp [ key ] != mat [ i ][ j ]) return false ; } // Else we put keyvalue pair in hashmap else { mp [ i - j ] = mat [ i ][ j ]; } } } return true ; } static void Main () { var mat = new List < List < int >> { new List < int > { 6 7 8 } new List < int > { 4 6 7 } new List < int > { 1 4 6 } }; if ( isToeplitz ( mat )) { Console . WriteLine ( 'Yes' ); } else { Console . WriteLine ( 'No' ); } } }
JavaScript // Function to check whether given // matrix is toeplitz matrix or not function isToeplitz ( mat ) { let n = mat . length m = mat [ 0 ]. length ; // HashMap to store keyvalue pairs const mp = new Map (); for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < m ; j ++ ) { let key = i - j ; // If key value exists in the hashmap if ( mp . has ( key )) { // check if the value is same // as the current element if ( mp . get ( key ) !== mat [ i ][ j ]) return false ; } // Else we put keyvalue pair in hashmap else { mp . set ( i - j mat [ i ][ j ]); } } } return true ; } let mat = [ [ 6 7 8 ] [ 4 6 7 ] [ 1 4 6 ] ]; if ( isToeplitz ( mat )) { console . log ( 'Yes' ); } else { console . log ( 'No' ); }
Saída
Yes
