Keresse meg, hogy az adott mátrix Toeplitz-e vagy sem
Adott egy négyzetmátrix együtt [][] a rend n az a feladatod, hogy ellenőrizze, hogy Toeplitz Mátrix-e.
Jegyzet: A Toeplitz-mátrix - más néven diagonális-konstans mátrix - egy olyan mátrix, amelyben minden egyes csökkenő átló elemei balról jobbra megegyeznek. Bármely belépőszőnyeg [i][j] esetében megegyezik a mat[i-1][j-1] vagy a mat[i-2][j-2] és son on-val.
Példák:
Bemenet: with[][] = [ [6 7 8]
[4 6 7]
[1 4 6] ]
Kimenet: Igen
Magyarázat: Az adott mátrix összes átlója [6 6 6] [7 7] [8] [4 4] [1]. Minden átlóhoz, mivel minden elem azonos, a megadott mátrix a Toeplitz mátrix.Bemenet: with[][] = [ [6 3 8]
[4 9 7]
[1 4 6] ]
Kimenet: Nem
Magyarázat: Az adott mátrix elsődleges átlós elemei [6 9 6]. Mivel az átlós elemek nem azonosak, az adott mátrix nem Toeplitz mátrix.
[Várható megközelítés - 1] - Minden átló ellenőrzése - O(n * n) idő és O(1) tér
Az ötlet az, hogy a mátrix minden lefelé dőlő átlóját bejárjuk úgy, hogy az első sor minden elemét és az első oszlop minden elemét használjuk kiindulási pontként, és ellenőrizzük, hogy az átló mentén minden elem megegyezik-e a fejénél lévő értékkel.
Kövesse az alábbi lépéseket:
- Hadd
n = mat.size()ésm = mat[0].size(). - Minden oszlopindexhez
i-tól0hogym - 1híváscheckDiagonal(mat 0 i); ha false-t ad vissza azonnal return false fromisToeplitz. - Minden sorindexhez
i-tól0hogyn - 1híváscheckDiagonal(mat i 0); ha false-t ad vissza azonnal return false fromisToeplitz. - Ha minden hívja
checkDiagonalsikerül visszatérni igaz. - In
checkDiagonal(mat x y)összehasonlítanimat[i][j]hogymat[x][y]mindegyikrei = x+1 j = y+1mígi < n && j < m; return false az első eltérésnél, ellenkező esetben az él elérése után visszatér igaz.
Az alábbiakban megadjuk a végrehajtás:
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' ); }
Kimenet
Yes
[Várható megközelítés - 2] - Ellenőrzés átlósan az elem felett - O(n * n) idő és O(1) tér
Az ötlet az, hogy a második sortól és a második oszloptól kezdve minden cellát átvizsgálunk, összehasonlítva az értékeket a bal felső szomszédjával. Ha bármely elem eltér az átlósan felette lévőtől, akkor a Toeplitz tulajdonság megsértését találta, és azonnal leállíthatja; ha a teljes mátrixon átjutsz nem illesztés nélkül, minden átló állandó.
Kövesse az alábbi lépéseket:
- Hadd
n = mat.size()ésm = mat[0].size(). - Hajtogat
i1-tőln - 1és azon belülj1-tőlm - 1. - Ha
mat[i][j] != mat[i - 1][j - 1]bármikor visszatérhetfalse. - Miután az összes pár ellenőrzése megtörtént, és nincs eltérés, visszatér
true.
Az alábbiakban megadjuk a végrehajtás:
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' ); }
Kimenet
Yes
[Alternatív megközelítés] – Kivonat használata – O(n * n) idő és O(n) tér
Az ötlet az, hogy minden jobb alsó átlóhoz egyedi azonosítót rendeljünk (a sorindex mínusz az oszlopindex), és egy hash-térkép segítségével rögzítsük az adott átlóhoz tartozó első értéket. A teljes mátrix átvizsgálása során minden cellához kiszámítja ezt a kulcsot, és vagy ellenőrizze, hogy megegyezik-e a tárolt értékkel, vagy ha új, tárolja azt. Egyetlen eltérés is lehetővé teszi, hogy kisegítse a hamisat; különben a végén igazat vonsz le.
Kövesse az alábbi lépéseket:
- Határozza meg a mátrix méreteit (sorszám és oszlopszám) ebből
mat. - Hozzon létre egy üres hashmapot
mphogy minden átlós kulcsot leképezzünk a reprezentatív értékükre. - Menj át minden cellán
matsorindexéveliés oszlopindexj. - Minden cellához kivonással alakítsuk ki az átlós kulcsot
j-tóli. - Ha
mpmár rendelkezik ezzel a kulccsal, és hasonlítsa össze az aktuális elemet a tárolt értékkel; ha eltérnek, azonnal hamis értéket adjon vissza. - Ha a kulcs még nincs bent
mprögzítse az aktuális elemet az adott kulcs alatt. - Ha a bejárást eltérés nélkül fejezi be, akkor adjon igazat.
Ábra:
Az alábbi diagram jobban szemlélteti ezt az ötletet. Tekintsük az átlós sárga színűt. Ezen az átlón bármely index x-értéke és y-értéke közötti különbség 2 (2-0 3-1 4-2 5-3). Ugyanez megfigyelhető minden testátlónál.
Piros színűnél az átló különbség 3. Zöld színűnél az átlókülönbség 0. A narancssárga színűnél -2 és így tovább...
Az alábbiakban megadjuk a végrehajtás:
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' ); }
Kimenet
Yes
