מצא אם המטריצה הנתונה היא Toeplitz או לא
נתון מטריצה מרובעת יחד עם [][] של סדר נ המשימה שלך היא לבדוק אם זה מטריצת Toeplitz.
פֶּתֶק: מטריצת טופליץ - הנקראת גם מטריצה אלכסונית-קבועה - היא מטריצה שבה אלמנטים של כל אלכסון יורד זהים משמאל לימין. באופן שווה עבור כל מחצלת כניסה[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]. עבור כל אלכסון מכיוון שכל האלמנטים זהים, המטריצה הנתונה היא מטריצת טופליץ.קֶלֶט: עם[][] = [ [6 3 8]
[4 9 7]
[1 4 6] ]
תְפוּקָה: לֹא
הֶסבֵּר: האלמנטים האלכסוניים העיקריים של המטריצה הנתונה הם [6 9 6]. מכיוון שהאלמנטים האלכסוניים אינם זהים, המטריצה הנתונה אינה מטריצת טופליץ.
[גישה צפויה - 1] - בדיקת כל אלכסון - O(n * n) זמן ו-O(1) רווח
הרעיון הוא לחצות כל אלכסון בשיפוע כלפי מטה במטריצה על ידי שימוש בכל אלמנט בשורה הראשונה ובכל אלמנט בעמודה הראשונה כנקודת התחלה ולוודא שכל אלמנט לאורך האלכסון הזה מתאים לערך שבראשו.
בצע את השלבים הבאים:
- לְאַפשֵׁר
n = mat.size()וm = mat[0].size(). - עבור כל אינדקס עמודה
iמִן0אֶלm - 1שִׂיחָהcheckDiagonal(mat 0 i); אם הוא מחזיר false מיד החזר false fromisToeplitz. - עבור כל אינדקס שורה
iמִן0אֶלn - 1שִׂיחָהcheckDiagonal(mat i 0); אם הוא מחזיר false מיד החזר false fromisToeplitz. - אם כל השיחות
checkDiagonalלהצליח לחזור אמיתי. - ב
checkDiagonal(mat x y)לְהַשְׁווֹתmat[i][j]אֶלmat[x][y]עבור כל אחדi = x+1 j = y+1בְּעוֹדi < n && j < m; החזר שקר בחוסר ההתאמה הראשון אחרת החזר אמת לאחר הגעה לקצה.
להלן ניתן את יישום:
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) רווח
הרעיון הוא להקצות מזהה ייחודי לכל אלכסון למטה מימין (אינדקס השורה פחות אינדקס העמודה) ולהשתמש במפת גיבוב כדי לתעד את הערך הראשון שנראה עבור אותו אלכסון. כשאתה סורק את המטריצה כולה אתה מחשב את המפתח הזה עבור כל תא ומוודא שהוא תואם לערך המאוחסן או אם הוא חדש מאחסן אותו. אי התאמה בודדת מאפשרת לך לחלץ עם שקר; אחרת אתה מסיק נכון בסוף.
בצע את השלבים הבאים:
- קבע את ממדי המטריצה (ספירת שורות וספירת עמודות).
mat. - צור מפת hashmap ריקה
mpלמפות כל מפתח אלכסוני לערך המייצג שלו. - תעבור דרך כל תא פנימה
matלפי מדד השורות שלוiואינדקס העמודותj. - עבור כל תא יוצרים את המפתח האלכסוני על ידי חיסור
jמִןi. - אִם
mpכבר מחזיק מפתח זה השווה את האלמנט הנוכחי לערך המאוחסן; אם הם שונים, החזר false מיד. - אם המפתח עדיין לא נמצא
mpרשום את האלמנט הנוכחי תחת המפתח הזה. - אם תשלים את המעבר ללא חוסר התאמה, החזר אמת.
אִיוּר:
התרשים שלהלן נותן הדמיה טובה יותר של רעיון זה. שקול את הצבע האלכסוני הצהוב. ההבדל בין ערך 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
