Encuentre si la matriz dada es Toeplitz o no
Dada una matriz cuadrada junto con[][] de orden norte su tarea es comprobar si se trata de una matriz de Toeplitz.
Nota: Una matriz de Toeplitz, también llamada matriz diagonal constante, es una matriz donde los elementos de cada diagonal descendente individual son iguales de izquierda a derecha. De manera equivalente, para cualquier entrada mat[i][j] es lo mismo que mat[i-1][j-1] o mat[i-2][j-2] y así sucesivamente.
Ejemplos:
Aporte: con[][] = [ [6 7 8]
[4 6 7]
[1 4 6] ]
Producción: Sí
Explicación: Todas las diagonales de la matriz dada son [6 6 6] [7 7] [8] [4 4] [1]. Para cada diagonal, ya que todos los elementos son iguales, la matriz dada es la Matriz de Toeplitz.Aporte: con[][] = [ [6 3 8]
[4 9 7]
[1 4 6] ]
Producción: No
Explicación: Los elementos diagonales primarios de la matriz dada son [6 9 6]. Como los elementos diagonales no son iguales, la matriz dada no es la Matriz de Toeplitz.
[Enfoque esperado - 1] - Comprobando cada diagonal - O(n * n) Tiempo y O(1) Espacio
La idea es recorrer cada diagonal con pendiente descendente en la matriz utilizando cada elemento de la primera fila y cada elemento de la primera columna como punto de partida y verificar que cada elemento a lo largo de esa diagonal coincida con el valor en su cabecera.
Siga los pasos que se indican a continuación:
- Dejar
n = mat.size()ym = mat[0].size(). - Para cada índice de columna
ide0am - 1llamarcheckDiagonal(mat 0 i); si devuelve falso inmediatamente devuelve falso deisToeplitz. - Para cada índice de fila
ide0an - 1llamarcheckDiagonal(mat i 0); si devuelve falso inmediatamente devuelve falso deisToeplitz. - Si todas las llamadas a
checkDiagonaltener éxito devuelve verdadero. - En
checkDiagonal(mat x y)compararmat[i][j]amat[x][y]para cada unoi = x+1 j = y+1mientrasi < n && j < m; devuelve falso en la primera discrepancia; de lo contrario, devuelve verdadero después de alcanzar el borde.
A continuación se da el implementación:
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' ); }
Producción
Yes
[Enfoque esperado - 2] - Comprobación del elemento diagonalmente encima - O(n * n) Tiempo y O(1) Espacio
La idea es escanear cada celda desde la segunda fila y la segunda columna en adelante comparando cada valor con su vecino superior izquierdo. Si algún elemento difiere del que está en diagonal encima, habrá encontrado una violación de la propiedad Toeplitz y puede detenerse inmediatamente; Si recorre toda la matriz sin desajustes, cada diagonal es constante.
Siga los pasos que se indican a continuación:
- Dejar
n = mat.size()ym = mat[0].size(). - Iterar
ide 1 an - 1y dentro de esojde 1 am - 1. - Si
mat[i][j] != mat[i - 1][j - 1]en cualquier momento regresarfalse. - Una vez que se hayan verificado todos los pares sin discrepancias, regrese
true.
A continuación se da el implementación:
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' ); }
Producción
Yes
[Enfoque alternativo] - Uso de hash - O(n * n) Tiempo y O(n) Espacio
La idea es asignar un identificador único a cada diagonal inferior derecha (el índice de fila menos el índice de columna) y utilizar un mapa hash para registrar el primer valor visto para esa diagonal. A medida que escanea toda la matriz, calcula esta clave para cada celda y verifica que coincida con el valor almacenado o, si es nueva, guárdela. Una sola discrepancia le permite salir del apuro con false; de lo contrario, al final concluirás que es cierto.
Siga los pasos que se indican a continuación:
- Determine las dimensiones de la matriz (recuento de filas y recuento de columnas) a partir de
mat. - Crear un mapa hash vacío
mppara asignar cada clave diagonal a su valor representativo. - Camina por cada celda en
matpor su índice de filaie índice de columnasj. - Para cada celda, forme la clave diagonal restando
jdei. - Si
mpya tiene esta clave compara el elemento actual con el valor almacenado; si difieren, devuelve falso inmediatamente. - Si la llave aún no está en
mpregistre el elemento actual bajo esa clave. - Si completa el recorrido sin ninguna discrepancia, devuelva verdadero.
Ilustración:
El siguiente diagrama ofrece una mejor visualización de esta idea. Considere la diagonal de color amarillo. La diferencia entre el valor de x y el valor de y de cualquier índice en esta diagonal es 2 (2-0 3-1 4-2 5-3). Lo mismo se puede observar para todas las diagonales del cuerpo.
Para el color rojo, la diferencia diagonal es 3. Para el color verde, la diferencia diagonal es 0. Para el color naranja, la diferencia diagonal es -2 y así sucesivamente...
A continuación se da el implementación:
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' ); }
Producción
Yes
