logo

TechCodeview

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:

  • Haddn = mat.size()ésm = mat[0].size().
  • Minden oszlopindexhezi-tól0hogym - 1híváscheckDiagonal(mat 0 i); ha false-t ad vissza azonnal return false fromisToeplitz.
  • Minden sorindexhezi-tól0hogyn - 1híváscheckDiagonal(mat i 0); ha false-t ad vissza azonnal return false fromisToeplitz.
  • Ha minden hívjacheckDiagonalsikerül visszatérni igaz.
  • IncheckDiagonal(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:

  • Haddn = mat.size()ésm = mat[0].size().
  • Hajtogati1-tőln - 1és azon belülj1-tőlm - 1.
  • Hamat[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értrue.

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őlmat.
  • Hozzon létre egy üres hashmapot mp hogy minden átlós kulcsot leképezzünk a reprezentatív értékükre.
  • Menj át minden cellánmatsorindexéveliés oszlopindexj.
  • Minden cellához kivonással alakítsuk ki az átlós kulcsotj-tóli.
  • Hampmá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 bentmprö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.

Keresse meg, hogy az adott mátrix Toeplitz-e vagy sem

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<intint> mp = new Dictionary<intint>();    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