Намерете дали дадената матрица е Toeplitz или не
Дадена е квадратна матрица заедно с [][] на реда п вашата задача е да проверите дали е Toeplitz Matrix.
Забележка: Матрицата на Тьоплиц - наричана още диагонално-постоянна матрица - е матрица, при която елементите на всеки отделен низходящ диагонал са еднакви отляво надясно. Еквивалентно за всеки запис mat[i][j] е същото като mat[i-1][j-1] или mat[i-2][j-2] и т.н.
Примери:
вход: с [][] = [ [6 7 8]
[4 6 7]
[1 4 6] ]
Изход: да
Обяснение: Всички диагонали на дадената матрица са [6 6 6] [7 7] [8] [4 4] [1]. За всеки диагонал, тъй като всички елементи са еднакви, дадената матрица е матрица на Toeplitz.вход: с [][] = [ [6 3 8]
[4 9 7]
[1 4 6] ]
Изход: не
Обяснение: Първичните диагонални елементи на дадената матрица са [6 9 6]. Тъй като диагоналните елементи не са еднакви, дадената матрица не е матрица на Toeplitz.
[Очакван подход - 1] - Проверка на всеки диагонал - O(n * n) време и O(1) пространство
Идеята е да се премине през всеки наклонен надолу диагонал в матрицата, като се използва всеки елемент в първия ред и всеки елемент в първата колона като начална точка и се проверява дали всеки елемент по този диагонал съответства на стойността в началото му.
Следвайте дадените по-долу стъпки:
- Нека
n = mat.size()иm = mat[0].size(). - За всеки индекс на колона
iот0къмm - 1обажданеcheckDiagonal(mat 0 i); ако върне false, веднага връща false отisToeplitz. - За всеки ред индекс
iот0къмn - 1обажданеcheckDiagonal(mat i 0); ако върне false, веднага връща false отisToeplitz. - Ако всички обаждания до
checkDiagonalуспех връщане вярно. - в
checkDiagonal(mat x y)сравнявамmat[i][j]къмmat[x][y]за всекиi = x+1 j = y+1докатоi < n && j < m; връща false при първото несъответствие, в противен случай връща true след достигане на ръба.
По-долу е дадено изпълнение:
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' ); }
Изход
Yes
[Очакван подход - 2] - Проверка по диагонал над елемента - O(n * n) време и O(1) пространство
Идеята е да се сканира всяка клетка от втория ред и втората колона нататък, като се сравнява всяка стойност с горния ляв съсед. Ако някой елемент се различава от този по диагонал над него, вие сте открили нарушение на свойството Toeplitz и можете да спрете незабавно; ако преминете през цялата матрица без несъответствие, всеки диагонал е постоянен.
Следвайте дадените по-долу стъпки:
- Нека
n = mat.size()иm = mat[0].size(). - Итерация
iот 1 доn - 1и в рамките на товаjот 1 доm - 1. - Ако
mat[i][j] != mat[i - 1][j - 1]във всяка точка се върнетеfalse. - След като всички двойки са проверени без несъответствия, се връща
true.
По-долу е дадено изпълнение:
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' ); }
Изход
Yes
[Алтернативен подход] - Използване на хеширане - O(n * n) време и O(n) пространство
Идеята е да се присвои уникален идентификатор на всеки диагонал надолу вдясно (индексът на реда минус индексът на колоната) и да се използва хеш карта, за да се запише първата стойност, видяна за този диагонал. Докато сканирате цялата матрица, вие изчислявате този ключ за всяка клетка и или проверявате дали съответства на съхранената стойност, или ако е нова, запазете я. Едно несъответствие ви позволява да спасите с false; иначе заключаваш, че е вярно накрая.
Следвайте дадените по-долу стъпки:
- Определете размерите на матрицата (брой редове и брой колони) от
mat. - Създайте празна hashmap
mpза съпоставяне на всеки диагонален ключ с неговата представителна стойност. - Преминете през всяка клетка
matпо неговия индекс на редаiи индекс на колонаj. - За всяка клетка формирайте диагоналния ключ чрез изваждане
jотi. - Ако
mpвече държи този ключ сравнява текущия елемент със съхранената стойност; ако се различават, незабавно връща false. - Ако ключът все още не е вътре
mpзапишете текущия елемент под този ключ. - Ако завършите преминаването без никакво несъответствие, върнете true.
Илюстрация:
Диаграмата по-долу дава по-добра визуализация на тази идея. Помислете за диагонала, оцветен в жълто. Разликата между x-стойността и y-стойността на всеки индекс на този диагонал е 2 (2-0 3-1 4-2 5-3). Същото може да се наблюдава за всички диагонали на тялото.
За червения диагонал разликата е 3. За зеления диагонал разликата е 0. За оранжевия диагонал разликата е -2 и така нататък...
По-долу е дадено изпълнение:
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' ); }
Изход
Yes
