给定一个方阵，找出它是否是托普利兹矩阵。Toeplitz（或对角常数）矩阵是一个矩阵，其中每个 从左到右成对角线 是常数，即对角线中的所有元素都相同。 一般来说，如果每个单元mat[i][j]与mat[i-1][j-1]、mat[i+1][j+1]、mat[i-2][j-2]、mat[i+2][j+2]相同，则任何n×n矩阵mat[]都是Toeplitz矩阵。。对于每个单元格mat[i][j]和所有有效单元格mat[i+k][j+k]或mat[i-k][j-k]
null
例如：
Input: mat[N][N] = {{ 6, 7, 8}, { 4, 6, 7}, { 1, 4, 6}},Output : True;Values in all diagonals are same.Input: mat[N][N] = {{ 6, 7, 8, 9 }, { 4, 6, 7, 8 }, { 1, 4, 6, 7 }, { 0, 1, 4, 6 }, { 2, 0, 1, 4 }};Output : True;Input: mat[N][N] = {{ 6, 3, 8}, { 4, 9, 7}, { 1, 4, 6}},Output : False;
这个想法很简单。对于矩阵中第一行和第一列（或最后一行和最后一列）的每个元素，我们检查从该元素开始的下行对角线是否具有相同的值。如果我们发现任何对角线具有不同的值，我们将返回false。
以下是上述代码的实现：
C++
// C++ program to check whether given matrix // is a Toeplitz matrix or not #include <iostream> using namespace std; #define N 5 #define M 4 // Function to check if all elements present in // descending diagonal starting from position // (i, j) in the matrix are all same or not bool checkDiagonal( int mat[N][M], int i, int j) { int res = mat[i][j]; while (++i < N && ++j < M) { // mismatch found if (mat[i][j] != res) return false ; } // we only reach here when all elements // in given diagonal are same return true ; } // Function to check whether given matrix is a // Toeplitz matrix or not bool isToeplitz( int mat[N][M]) { // do for each element in first row for ( int i = 0; i < M; i++) { // check descending diagonal starting from // position (0, j) in the matrix if (!checkDiagonal(mat, 0, i)) return false ; } // do for each element in first column for ( int i = 1; i < N; i++) { // check descending diagonal starting from // position (i, 0) in the matrix if (!checkDiagonal(mat, i, 0)) return false ; } // we only reach here when each descending // diagonal from left to right is same return true ; } // Driver code int main() { int mat[N][M] = { { 6, 7, 8, 9 }, { 4, 6, 7, 8 }, { 1, 4, 6, 7 }, { 0, 1, 4, 6 }, { 2, 0, 1, 4 } }; // Function call if (isToeplitz(mat)) cout << "Matrix is a Toeplitz " ; else cout << "Matrix is not a Toeplitz " ; return 0; } |
JAVA
// Java program to check whether given matrix // is a Toeplitz matrix or not import java.io.*; class GFG { public static int N = 5 ; public static int M = 4 ; // Function to check if all elements present in // descending diagonal starting from position // (i, j) in the matrix are all same or not static boolean checkDiagonal( int mat[][], int i, int j) { int res = mat[i][j]; while (++i < N && ++j < M) { // mismatch found if (mat[i][j] != res) return false ; } // we only reach here when all elements // in given diagonal are same return true ; } // Function to check whether given matrix is a // Toeplitz matrix or not static boolean isToeplitz( int mat[][]) { // do for each element in first row for ( int i = 0 ; i < M; i++) { // check descending diagonal starting from // position (0, j) in the matrix if (!checkDiagonal(mat, 0 , i)) return false ; } // do for each element in first column for ( int i = 1 ; i < N; i++) { // check descending diagonal starting from // position (i, 0) in the matrix if (!checkDiagonal(mat, i, 0 )) return false ; } // we only reach here when each descending // diagonal from left to right is same return true ; } // Driver code public static void main(String[] args) { int mat[][] = { { 6 , 7 , 8 , 9 }, { 4 , 6 , 7 , 8 }, { 1 , 4 , 6 , 7 }, { 0 , 1 , 4 , 6 }, { 2 , 0 , 1 , 4 } }; // Function call if (isToeplitz(mat)) System.out.println( "Matrix is a Toeplitz " ); else System.out.println( "Matrix is not a Toeplitz " ); } } // This code is contributed by Pramod Kumar |
Python3
# Python3 program to check whether given # matrix is a Toeplitz matrix or not N = 5 M = 4 # Function to check if all elements present in # descending diagonal starting from position # (i, j) in the matrix are all same or not def checkDiagonal(mat, i, j): res = mat[i][j] i + = 1 j + = 1 while (i < N and j < M): # mismatch found if (mat[i][j] ! = res): return False i + = 1 j + = 1 # we only reach here when all elements # in given diagonal are same return True # Function to check whether given # matrix is a Toeplitz matrix or not def isToeplitz(mat): # do for each element in first row for j in range (M): # check descending diagonal starting from # position (0, j) in the matrix if not (checkDiagonal(mat, 0 , j)): return False # do for each element in first column for i in range ( 1 , N): # check descending diagonal starting # from position (i, 0) in the matrix if not (checkDiagonal(mat, i, 0 )): return False return True # Driver Code if __name__ = = "__main__" : mat = [[ 6 , 7 , 8 , 9 ], [ 4 , 6 , 7 , 8 ], [ 1 , 4 , 6 , 7 ], [ 0 , 1 , 4 , 6 ], [ 2 , 0 , 1 , 4 ]] # Function call if (isToeplitz(mat)): print ( "Matrix is a Toeplitz" ) else : print ( "Matrix is not a Toeplitz" ) # This code is contributed by Jasmine K Grewal |
C#
// C# program to check whether given matrix // is a Toeplitz matrix or not using System; class GFG { public static int N = 5; public static int M = 4; // Function to check if all elements present in // descending diagonal starting from position // (i, j) in the matrix are all same or not static bool checkDiagonal( int [, ] mat, int i, int j) { int res = mat[i, j]; while (++i < N && ++j < M) { // mismatch found if (mat[i, j] != res) return false ; } // we only reach here when all elements // in given diagonal are same return true ; } // Function to check whether given matrix is a // Toeplitz matrix or not static bool isToeplitz( int [, ] mat) { // do for each element in first row for ( int i = 0; i < M; i++) { // check descending diagonal starting from // position (0, j) in the matrix if (!checkDiagonal(mat, 0, i)) return false ; } // do for each element in first column for ( int i = 1; i < N; i++) { // check descending diagonal starting from // position (i, 0) in the matrix if (!checkDiagonal(mat, i, 0)) return false ; } // we only reach here when each descending // diagonal from left to right is same return true ; } // Driver code public static void Main() { int [, ] mat = { { 6, 7, 8, 9 }, { 4, 6, 7, 8 }, { 1, 4, 6, 7 }, { 0, 1, 4, 6 }, { 2, 0, 1, 4 } }; // Function call if (isToeplitz(mat)) Console.WriteLine( "Matrix is a Toeplitz " ); else Console.WriteLine( "Matrix is not a Toeplitz " ); } } // This code is contributed by KRV. |
PHP
<?php // PHP program to check whether // given matrix is a Toeplitz // matrix or not // Function to check if all // elements present in descending // diagonal starting from position // (i, j) in the matrix are all // same or not function checkDiagonal( $mat , $i , $j ) { $N = 5; $M = 4; $res = $mat [ $i ][ $j ]; while (++ $i < $N && ++ $j < $M ) { // mismatch found if ( $mat [ $i ][ $j ] != $res ) return false; } // we only reach here when // all elements in given // diagonal are same return true; } // Function to check whether // given matrix is a // Toeplitz matrix or not function isToeplitz( $mat ) { $N = 5; $M = 4; // do for each element in first row for ( $i = 0; $i < $M ; $i ++) { // check descending diagonal // starting from position // (0, j) in the matrix if (!checkDiagonal( $mat , 0, $i )) return false; } // do for each element // in first column for ( $i = 1; $i < $N ; $i ++) { // check descending diagonal // starting from position // (i, 0) in the matrix if (!checkDiagonal( $mat , $i , 0)) return false; } // we only reach here when // each descending diagonal // from left to right is same return true; } // Driver code $mat = array ( array ( 6, 7, 8, 9 ), array ( 4, 6, 7, 8 ), array ( 1, 4, 6, 7 ), array ( 0, 1, 4, 6 ), array ( 2, 0, 1, 4 )); // Function call if (isToeplitz( $mat )) echo "Matrix is a Toeplitz " ; else echo "Matrix is not a Toeplitz " ; // This code is contributed // by nitin mittal. ?> |
Javascript
<script> // Javascript program to check whether given matrix // is a Toeplitz matrix or not let N = 5; let M = 4; // Function to check if all elements present in // descending diagonal starting from position // (i, j) in the matrix are all same or not function checkDiagonal(mat, i, j) { let res = mat[i][j]; while (++i < N && ++j < M) { // mismatch found if (mat[i][j] != res) return false ; } // we only reach here when all elements // in given diagonal are same return true ; } // Function to check whether given matrix is a // Toeplitz matrix or not function isToeplitz(mat) { // do for each element in first row for (let i = 0; i < M; i++) { // check descending diagonal starting from // position (0, j) in the matrix if (!checkDiagonal(mat, 0, i)) return false ; } // do for each element in first column for (let i = 1; i < N; i++) { // check descending diagonal starting from // position (i, 0) in the matrix if (!checkDiagonal(mat, i, 0)) return false ; } // we only reach here when each descending // diagonal from left to right is same return true ; } let mat = [ [ 6, 7, 8, 9 ], [ 4, 6, 7, 8 ], [ 1, 4, 6, 7 ], [ 0, 1, 4, 6 ], [ 2, 0, 1, 4 ] ]; // Function call if (isToeplitz(mat)) document.write( "Matrix is a Toeplitz " ); else document.write( "Matrix is not a Toeplitz " ); </script> |
输出
Matrix is a Toeplitz
这个 时间复杂性 这个解的形式是O（n） 2. )因为我们只遍历矩阵中的每个元素一次。 参考： https://en.wikipedia.org/wiki/Toeplitz_matrix
基于哈希的方法：
考虑维度（m，n）矩阵的索引（i，j）中的元素。为了使矩阵是对角常数，对角线上的所有元素必须相同。考虑包含这个（i，j）元素的对角线。对角线中的其他元素的索引形式为（i+k，j+k）或（i-k，j-k）。请注意，无论这些索引的x值和y值是什么，它们的差异总是相同的。i、 e.（i+k）-（j+k）==（i-k）-（j-k）==i-j。
下图更好地展示了这个想法。考虑对角线黄色。对角线上任何指数的x值和y值之差为2（2-0，3-1，4-2，5-3）。所有身体对角线都可以观察到同样的情况。
![图片[1]-找出给定的矩阵是否为Toeplitz-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20200707/geeks_toep-300x300.png)
Toeplitz矩阵的指数
对于红色对角线，差异为3。对于绿色对角线，差值为0。对于橙色对角线，差为-2，以此类推…
其想法是利用这样一个事实，即对于托普利兹矩阵，特定对角线的这些单独索引差异将是唯一的。因为它是一个常数对角线矩阵，对于所有这些唯一的键，应该有唯一的值，和对角线上的任何元素一样。因此，我们创建一个HashMap来存储这些（键、值）对。在任何时刻，如果我们遇到一个不同于其相应存储键值的值，我们都会返回false。
以下是上述代码的实现：
C++
// C++ program to check whether given // matrix is a Toeplitz matrix or not #include <bits/stdc++.h> using namespace std; bool isToeplitz(vector<vector< int >> matrix) { // row = number of rows // col = number of columns int row = matrix.size(); int col = matrix[0].size(); // HashMap to store key,value pairs map< int , int > Map; 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[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[key] != matrix[i][j]) return false ; } // Else we put key,value pair in hashmap else { Map[i - j] = matrix[i][j]; } } } return true ; } // Driver code int main() { vector<vector< int >> matrix = { { 12, 23, -32 }, { -20, 12, 23 }, { 56, -20, 12 }, { 38, 56, -20 } }; // Function call string result = (isToeplitz(matrix)) ? "Yes" : "No" ; cout << result; return 0; } // This code is contributed by divyesh072019 |
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 key,value 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 key,value 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); } } |
Python3
# 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 key,value 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 key,value 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#
// C# program to check whether given // matrix is a Toeplitz matrix or not using System; using System.Collections.Generic; class GFG{ static bool isToeplitz( int [,] matrix) { // row = number of rows // col = number of columns int row = matrix.GetLength(0); int col = matrix.GetLength(1); // HashMap to store key,value pairs Dictionary< int , int > map = new Dictionary< int , int >(); 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[key] != matrix[i, j]) return false ; } // Else we put key,value pair in hashmap else { map.Add(i - j, matrix[i, j]); } } } return true ; } // Driver code static void Main() { int [,] matrix = { { 12, 23, -32 }, { -20, 12, 23 }, { 56, -20, 12 }, { 38, 56, -20 } }; // Function call string result = (isToeplitz(matrix)) ? "Yes" : "No" ; Console.WriteLine(result); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // JavaScript program to check whether given // matrix is a Toeplitz matrix or not function isToeplitz(matrix) { // row = number of rows // col = number of columns let row = matrix.length; let col = matrix[0].length; // HashMap to store key,value pairs let map = new Map(); for (let i = 0; i < row; i++) { for (let j = 0; j < col; j++) { let key = i - j; // If key value exists in the hashmap, if (map.has(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 key,value pair in hashmap else { map.set(i - j, matrix[i][j]); } } } return true ; } // Driver code let matrix = [ [ 12, 23, -32 ], [ -20, 12, 23 ], [ 56, -20, 12 ], [38, 56, -20 ] ]; // Function call let result = (isToeplitz(matrix)) ? "Yes" : "No" ; document.write(result); </script> |
输出
Yes
时间复杂性： O（明尼苏达州） ，其中m是行数，n是列数。 空间复杂性： O（m+n） ，因为在最坏的情况下，如果一个矩阵是Toeplitz，我们精确地存储了（m+n-1）个键，值对。（在第一行中，我们有n个不同的键，然后在接下来的每m-1行中，我们不断向地图添加一个唯一的键。
本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
