Find if given matrix is Toeplitz or not - GeeksforGeeks
Given a square matrix, find if it's a Toeplitz matrix or not. A Toeplitz (or diagonal-constant) matrix is a matrix in which each descending diagonal from left to right is constant, i.e., all elements in a diagonal are same.
In general, any n×n matrix mat[][] is a Toeplitz matrix if every cell mat[i][j] is same as mat[i-1][j-1], mat[i+1][j+1], mat[i-2][j-2], mat[i+2][j+2], .. for every cell mat[i][j] and all the valid cells mat[i+k][j+k] or mat[i-k][j-k]
http://www.1point3acres.com/bbs/thread-209141-1-1.html
判断toeplitz maxtrix, follow up 是矩阵很大怎么办
我说的是分成几块然后记录边界的值
矩阵很大的话一行一行读就可以了
只要判断i行和i+1行关系就行了
啊应该就一部分一部分load这个矩阵 然后把最下面和最右边的一列记下来就行了,楼上的那个同学讲的对的
面试官说了也可能矩阵大到只能load一行的一部分
复杂度的话虽然都是O(mn)，但是最好尽可能减少那个常数项 他说的是seek time
我觉得他的意思就是想只要比较一个元素和他右下方元素的大小就行了
Read full article from Find if given matrix is Toeplitz or not - GeeksforGeeks
Given a square matrix, find if it's a Toeplitz matrix or not. A Toeplitz (or diagonal-constant) matrix is a matrix in which each descending diagonal from left to right is constant, i.e., all elements in a diagonal are same.
In general, any n×n matrix mat[][] is a Toeplitz matrix if every cell mat[i][j] is same as mat[i-1][j-1], mat[i+1][j+1], mat[i-2][j-2], mat[i+2][j+2], .. for every cell mat[i][j] and all the valid cells mat[i+k][j+k] or mat[i-k][j-k]
// Function to check if all elements present in// descending diagonal starting from position// (i, j) in the matrix are all same or notbool 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 notbool isToepliz(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;}http://www.1point3acres.com/bbs/thread-209141-1-1.html
判断toeplitz maxtrix, follow up 是矩阵很大怎么办
我说的是分成几块然后记录边界的值
矩阵很大的话一行一行读就可以了
只要判断i行和i+1行关系就行了
啊应该就一部分一部分load这个矩阵 然后把最下面和最右边的一列记下来就行了,楼上的那个同学讲的对的
面试官说了也可能矩阵大到只能load一行的一部分
复杂度的话虽然都是O(mn)，但是最好尽可能减少那个常数项 他说的是seek time
我觉得他的意思就是想只要比较一个元素和他右下方元素的大小就行了
Read full article from Find if given matrix is Toeplitz or not - GeeksforGeeks
