logo

TechCodeview

Find om givet matrix er Toeplitz eller ej

Givet en kvadratisk matrix sammen med[][] af orden n din opgave er at tjekke om det er en Toeplitz Matrix.

alfabetets tal

Note: En Toeplitz matrix - også kaldet en diagonal-konstant matrix - er en matrix, hvor elementer i hver enkelt faldende diagonal er ens fra venstre mod højre. Tilsvarende for enhver indgangsmåtte[i][j] er det det samme som mat[i-1][j-1] eller mat[i-2][j-2] og søn på.



Eksempler:

Input: med[][] = [ [6 7 8]
[4 6 7]
[1 4 6] ]
Produktion: Ja
Forklaring: Alle diagonalerne i den givne matrix er [6 6 6] [7 7] [8] [4 4] [1]. For hver diagonal, da alle elementerne er ens, er den givne matrix Toeplitz Matrix.

Input: med[][] = [ [6 3 8]
[4 9 7]
[1 4 6] ]
Produktion: Ingen
Forklaring: De primære diagonale elementer i den givne matrix er [6 9 6]. Da de diagonale elementer ikke er ens, er den givne matrix ikke Toeplitz Matrix.



[Forventet tilgang - 1] - Kontrol af hver diagonal - O(n * n) Tid og O(1) Mellemrum

Ideen er at krydse hver nedadgående diagonal i matricen ved at bruge hvert element i den første række og hvert element i den første kolonne som udgangspunkt og kontrollere, at hvert element langs denne diagonal matcher værdien i hovedet.

bibliotek omdøb linux

Følg nedenstående givne trin:

  • Laden = mat.size()ogm = mat[0].size().
  • For hver kolonneindeksifra0tilm - 1opkaldcheckDiagonal(mat 0 i); hvis den returnerer false, returnerer den straks falsk fraisToeplitz.
  • For hver række indeksifra0tiln - 1opkaldcheckDiagonal(mat i 0); hvis den returnerer false, returnerer den straks falsk fraisToeplitz.
  • Hvis alle kalder tilcheckDiagonallykkes returnere sandt.
  • IcheckDiagonal(mat x y)sammenlignemat[i][j]tilmat[x][y]for hveri = x+1 j = y+1mensi < n && j < m; returner falsk ved første mismatch ellers returnerer sand efter at have nået kanten.

Nedenfor er angivet implementering:



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'); }

Produktion 
Yes

[Forventet tilgang - 2] - Kontrol diagonalt over element - O(n * n) Tid og O(1) Mellemrum

Ideen er at scanne hver celle fra anden række og anden kolonne og fremefter sammenligne hver værdi med dens øverste venstre nabo. Hvis et element adskiller sig fra det ene diagonalt over det, har du fundet en krænkelse af Toeplitz-egenskaben og kan stoppe med det samme; hvis du kommer igennem hele matrixen uden uoverensstemmelse, er hver diagonal konstant.

Følg nedenstående givne trin:

  • Laden = mat.size()ogm = mat[0].size().
  • Gentagifra 1 tiln - 1og indenfor detjfra 1 tilm - 1.
  • Hvismat[i][j] != mat[i - 1][j - 1]på ethvert tidspunkt vende tilbagefalse.
  • Når alle par er blevet kontrolleret uden uoverensstemmelser, vender du tilbagetrue.

Nedenfor er angivet implementering:

sagde Madhuri
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'); }

Produktion 
Yes

[Alternativ tilgang] - Brug af hashing - O(n * n) Tid og O(n) Mellemrum

Ideen er at tildele en unik identifikator til hver diagonal nede til højre (rækkeindekset minus kolonneindekset) og bruge et hash-kort til at registrere den første værdi, der ses for den diagonal. Når du scanner hele matrixen, beregner du denne nøgle for hver celle og verificerer enten, at den matcher den lagrede værdi, eller om den er ny, gemmer du den. Et enkelt mismatch lader dig redde med falsk; ellers konkluderer du sandt til sidst.

Følg nedenstående givne trin:

  • Bestem matrixdimensionerne (rækkeantal og kolonneantal) framat.
  • Opret et tomt hashmap mp at kortlægge hver diagonalnøgle til dens repræsentative værdi.
  • Gå gennem hver celle indmatefter dets rækkeindeksiog kolonneindeksj.
  • For hver celle danner den diagonale nøgle ved at trække frajfrai.
  • Hvismpallerede holder denne tast sammenligne det aktuelle element med den lagrede værdi; hvis de adskiller sig returner falsk straks.
  • Hvis nøglen ikke er i endnumpoptag det aktuelle element under denne nøgle.
  • Hvis du fuldfører gennemgangen uden uoverensstemmelse, returneres sand.

Illustration:

shloka mehta uddannelse

Diagrammet nedenfor giver en bedre visualisering af denne idé. Overvej den diagonale farvet gul. Forskellen mellem x-værdi og y-værdi for ethvert indeks på denne diagonal er 2 (2-0 3-1 4-2 5-3). Det samme kan observeres for alle kropsdiagonaler.

Find om givet matrix er Toeplitz eller ej

For rød-farvet diagonal forskel er 3. For grøn-farvet diagonal forskel er 0. For orange-farvet diagonal forskel er -2 og så videre...

Nedenfor er angivet implementering:

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'); }

Produktion 
Yes