logo

TechCodeview

Descubra se determinada matriz é Toeplitz ou não

Dada uma matriz quadrada juntamente com[][] de ordem n sua tarefa é verificar se é uma matriz Toeplitz.

Observação: Uma matriz Toeplitz - também chamada de matriz constante diagonal - é uma matriz onde os elementos de cada diagonal descendente individual são iguais da esquerda para a direita. Equivalentemente, para qualquer entrada mat[i][j] é o mesmo que mat[i-1][j-1] ou mat[i-2][j-2] e assim por diante.



Exemplos:

Entrada: com[][] = [ [6 7 8]
[4 6 7]
[146]]
Saída: Sim
Explicação: Todas as diagonais da matriz dada são [6 6 6] [7 7] [8] [4 4] [1]. Para cada diagonal, como todos os elementos são iguais, a matriz fornecida é a Matriz Toeplitz.

Entrada: com[][] = [ [6 3 8]
[4 9 7]
[146]]
Saída: Não
Explicação: Os elementos diagonais primários da matriz dada são [6 9 6]. Como os elementos diagonais não são iguais, a matriz fornecida não é a Matriz Toeplitz.



[Abordagem esperada - 1] - Verificando cada diagonal - O(n * n) Tempo e O(1) Espaço

A ideia é percorrer cada diagonal inclinada para baixo na matriz usando cada elemento na primeira linha e cada elemento na primeira coluna como ponto de partida e verificar se cada elemento ao longo dessa diagonal corresponde ao valor em sua cabeça.

Siga as etapas abaixo:

  • Deixarn = mat.size()em = mat[0].size().
  • Para cada índice de colunaide0param - 1chamarcheckDiagonal(mat 0 i); se retornar falso retorne imediatamente falso deisToeplitz.
  • Para cada índice de linhaide0paran - 1chamarcheckDiagonal(mat i 0); se retornar falso retorne imediatamente falso deisToeplitz.
  • Se todas as chamadas paracheckDiagonalsucesso retornar verdadeiro.
  • EmcheckDiagonal(mat x y)compararmat[i][j]paramat[x][y]para cadai = x+1 j = y+1enquantoi < n && j < m; retorne falso na primeira incompatibilidade, caso contrário, retorne verdadeiro após atingir o limite.

Abaixo é dado o implementação:



string java conté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'); }

Saída 
Yes

[Abordagem esperada - 2] - Verificando diagonalmente acima do elemento - O(n * n) Tempo e O(1) Espaço

A ideia é varrer cada célula da segunda linha e da segunda coluna em diante, comparando cada valor com seu vizinho superior esquerdo. Se algum elemento for diferente daquele que está diagonalmente acima dele, você encontrou uma violação da propriedade Toeplitz e pode parar imediatamente; se você percorrer toda a matriz sem incompatibilidade, todas as diagonais serão constantes.

Siga as etapas abaixo:

  • Deixarn = mat.size()em = mat[0].size().
  • Iteraride 1 an - 1e dentro dissojde 1 am - 1.
  • Semat[i][j] != mat[i - 1][j - 1]a qualquer momento retornarfalse.
  • Depois que todos os pares forem verificados sem incompatibilidades, retornetrue.

Abaixo é dado o implementação:

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

Saída 
Yes

[Abordagem Alternativa] - Usando Hashing - O(n * n) Tempo e O(n) Espaço

A ideia é atribuir um identificador exclusivo a cada diagonal inferior direita (o índice da linha menos o índice da coluna) e usar um mapa hash para registrar o primeiro valor visto para aquela diagonal. Ao digitalizar toda a matriz, você calcula essa chave para cada célula e verifica se ela corresponde ao valor armazenado ou se é nova, armazena-a. Uma única incompatibilidade permite que você abandone o falso; caso contrário, você conclui verdadeiro no final.

Siga as etapas abaixo:

  • Determine as dimensões da matriz (contagem de linhas e contagem de colunas) demat.
  • Crie um hashmap vazio mp para mapear cada chave diagonal para seu valor representativo.
  • Percorra cada célula emmatpelo seu índice de linhaie índice de colunaj.
  • Para cada célula forme a chave diagonal subtraindojdei.
  • Sempjá contém esta chave compara o elemento atual com o valor armazenado; se forem diferentes, retorne falso imediatamente.
  • Se a chave ainda não estiver emmpregistre o elemento atual sob essa chave.
  • Se você concluir a travessia sem nenhuma incompatibilidade, retorne verdadeiro.

Ilustração:

O diagrama abaixo dá uma melhor visualização dessa ideia. Considere a diagonal colorida em amarelo. A diferença entre o valor x e o valor y de qualquer índice nesta diagonal é 2 (2-0 3-1 4-2 5-3). O mesmo pode ser observado para todas as diagonais do corpo.

Descubra se determinada matriz é Toeplitz ou não

Para a cor vermelha a diferença diagonal é 3. Para a cor verde a diferença diagonal é 0. Para a cor laranja a diferença diagonal é -2 e assim por diante...

meu flicker

Abaixo é dado o implementação:

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

Saída 
Yes