LeetCode 498 - Diagonal Traverse
http://lintcode.peqiu.com/content/lintcode/matrix_zigzag_traversal.html
Related:
http://rosettacode.org/wiki/Zig-zag_matrix#Java
http://www.cnblogs.com/EdwardLiu/p/6359701.html
http://lintcode.peqiu.com/content/lintcode/matrix_zigzag_traversal.html
- lintcode: (185) Matrix Zigzag Traversal
Given a matrix of m x n elements (m rows, n columns),
return all elements of the matrix in ZigZag-order.
Example
Given a matrix:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10, 11, 12]
]
return [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]
题解
按之字形遍历矩阵,纯粹找下标规律。以题中所给范例为例,设
(x, y)
为矩阵坐标,按之字形遍历有如下规律:(0, 0)
(0, 1), (1, 0)
(2, 0), (1, 1), (0, 2)
(0, 3), (1, 2), (2, 1)
(2, 2), (1, 3)
(2, 3)
可以发现其中每一行的坐标之和为常数,坐标和为奇数时 x 递增,为偶数时 x 递减。
Java - valid matrix index second public int[] printZMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0) return null;
int m = matrix.length - 1, n = matrix[0].length - 1;
int[] result = new int[(m + 1) * (n + 1)];
int index = 0;
for (int i = 0; i <= m + n; i++) {
if (i % 2 == 0) {
for (int x = i; x >= 0; x--) {
// valid matrix index
if ((x <= m) && (i - x <= n)) {
result[index] = matrix[x][i - x];
index++;
}
}
} else {
for (int x = 0; x <= i; x++) {
if ((x <= m) && (i - x <= n)) {
result[index] = matrix[x][i - x];
index++;
}
}
}
}
return result;
}
Java - valid matrix index first public int[] printZMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0) return null;
int m = matrix.length - 1, n = matrix[0].length - 1;
int[] result = new int[(m + 1) * (n + 1)];
int index = 0;
for (int i = 0; i <= m + n; i++) {
int upperBoundx = Math.min(i, m); // x <= m
int lowerBoundx = Math.max(0, i - n); // lower bound i - x(y) <= n
int upperBoundy = Math.min(i, n); // y <= n
int lowerBoundy = Math.max(0, i - m); // i - y(x) <= m
if (i % 2 == 0) {
// column increment
for (int y = lowerBoundy; y <= upperBoundy; y++) {
result[index] = matrix[i - y][y];
index++;
}
} else {
// row increment
for (int x = lowerBoundx; x <= upperBoundx; x++) {
result[index] = matrix[x][i - x];
index++;
}
}
}
return result;
}
矩阵行列和分奇偶讨论,奇数时行递增,偶数时列递增,一种是先循环再判断索引是否合法,另一种是先取的索引边界。
后判断索引是否合法的实现遍历次数为
, 首先确定上下界的每个元素遍历一次,时间复杂度 . 空间复杂度都是 .
http://cherylintcode.blogspot.com/2015/07/matrix-zigzag-traversal.html
public int[] printZMatrix(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return null;
int m = matrix.length, n = matrix[0].length;
int[] res = new int[m*n];
int j = 0;
for(int i = 0; i < m + n - 1; i++){
if(i % 2 == 1){
for(int y = Math.min(i, n - 1); y >= Math.max(0, i - m + 1); y--){
res[j++] = matrix[i-y][y];
}
} else{
for(int x = Math.min(i, m - 1); x >= Math.max(0, i - n + 1); x--){
res[j++] = matrix[x][i-x];
}
}
}
return res;
}
http://blog.csdn.net/wutingyehe/article/details/46629087
public int[] printZMatrix(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return null;
int count = matrix.length * matrix[0].length;
int[] array = new int[count];
int r = 0, c = 0;
array[0] = matrix[0][0];
for (int i = 1; i < count; ) {
//斜上走到顶
while(i < count && r - 1 >= 0 && c + 1 < matrix[0].length) {
array[i++] = matrix[--r][++c];
}
//横右走一步,不可横右走时竖下走一步
if (i < count && c + 1 < matrix[0].length) {
array[i++] = matrix[r][++c];
} else if (i < count && r + 1 < matrix.length) {
array[i++] = matrix[++r][c];
}
//斜下走到底
while(i < count && r + 1 < matrix.length && c - 1 >= 0) {
array[i++] = matrix[++r][--c];
}
//竖下走一步,不可竖下走时横右走一步
if (i < count && r + 1 < matrix.length) {
array[i++] = matrix[++r][c];
} else if (i < count && c + 1 < matrix[0].length) {
array[i++] = matrix[r][++c];
}
}
return array;
}public int[] printZMatrix(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return null;
int m = matrix.length, n = matrix[0].length;
int[] res = new int[m*n];
int j = 0;
for(int i = 0; i < m + n - 1; i++){
if(i % 2 == 1){
for(int y = Math.min(i, n - 1); y >= Math.max(0, i - m + 1); y--){
res[j++] = matrix[i-y][y];
}
} else{
for(int x = Math.min(i, m - 1); x >= Math.max(0, i - n + 1); x--){
res[j++] = matrix[x][i-x];
}
}
}
return res;
}
http://blog.csdn.net/wutingyehe/article/details/46629087
Related:
http://rosettacode.org/wiki/Zig-zag_matrix#Java
public static int[][] Zig_Zag(final int size) { int[][] data = new int[size][size]; int i = 1; int j = 1; for (int element = 0; element < size * size; element++) { data[i - 1][j - 1] = element; if ((i + j) % 2 == 0) { // Even stripes if (j < size) j++; else i+= 2; if (i > 1) i--; } else { // Odd stripes if (i < size) i++; else j+= 2; if (j > 1) j--; } } return data; }
http://www.cnblogs.com/EdwardLiu/p/6359701.html
7 static void print(int rows, int cols) { 8 int limit = rows * cols; 9 int T = rows * 2; // cycle 10 for (int i=1; i<=rows; i++) { 11 int[] curRow = new int[cols]; 12 int k = 0; 13 int index = 0; 14 while (k * T + i <= limit || k * T + T - i + 1 <= limit) { 15 if (k * T + i <= limit) curRow[index++] = k * T + i; 16 if (k * T + T - i + 1 <= limit) curRow[index++] = k * T + T - i + 1; 17 k++; 18 } 19 System.out.println(Arrays.toString(curRow)); 20 } 21 22 }