Matrix Zigzag Traversal 185
Question
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]
Solution
沿着斜线往上走,往下走,再往上走。。。直到最后一个元素。用dx,dy来控制走的方向,每次走到上下边界之后就换方向。
代码如下:
public class Solution {
/**
* @param matrix: a matrix of integers
* @return: an array of integers
*/
public int[] printZMatrix(int[][] matrix) {
// write your code here
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return new int[0];
}
int m = matrix.length;
int n = matrix[0].length;
int[] res = new int[m * n];
res[0] = matrix[0][0];
int count = 1;
int x = 0;
int y = 0;
int dx = -1;
int dy = 1;
while(count < m * n){
if(x + dx >= 0 && y + dy >= 0 && x + dx < m && y + dy < n){
//如果还没走到头,则继续往斜上方或者斜下方走
x = x + dx;
y = y + dy;
}else{
//往上走走到头
if(dx == -1 && dy == 1){
//如果还能向右移动则向右移,不行就向下移
if(y + dy < n){
y++;
}else{
x++;
}
dx = 1;
dy = -1;
}else{//往下走走到头
//如果还能向下移动则向下移,否则向右移
if(x + dx < m){
x++;
}else{
y++;
}
dx = -1;
dy = 1;
}
}
res[count++] = matrix[x][y];
}
return res;
}
}