Description

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

i = 0往右走或者往下走，然后往左下角走
j = 0往下走或者往右走，然后往右上角走
i = n - 1往右走，然后往右上角走
j = m - 1往下走，然后往左下角走

public class Solution {
    /*
     * @param matrix: An array of integers
     * @return: An array of integers
     */
    public int[] printZMatrix(int[][] matrix) {
        // write your code here
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return new int[0];
        }

        int n = matrix.length;
        int m = matrix[0].length;
        int[] ret = new int[n * m];
        ret[0] = matrix[0][0];
        int index = 1;
        int row = 0;
        int column = 0;
        boolean direction = false;
        while (index < m * n) {
            if (row == 0) {
                if (column < m - 1) {
                    ret[index++] = matrix[row][++column];
                } else if (row < n - 1) {
                    ret[index++] = matrix[++row][column];
                }
            } else if (column == 0) {
                if (row < n - 1) {
                    ret[index++] = matrix[++row][column];
                } else if (column < m - 1) {
                    ret[index++] = matrix[row][++column];
                }
            } else if (row == n - 1) {
                if (column < m - 1) {
                    ret[index++] = matrix[row][++column];
                }
            } else if (column == m - 1) {
                if (row < n - 1) {
                    ret[index++] = matrix[++row][column];
                }
            }

            if (row == 0 || column == 0 || row == n - 1 || column == m - 1) {
                direction = !direction;
            }

            if (direction) { //left-bottom
                if (row < n - 1 && column > 0) {
                    ret[index++] = matrix[++row][--column];
                }
            } else { //right top
                if (column < m - 1 && row > 0) {
                    ret[index++] = matrix[--row][++column];
                }
            }
        }

        return ret;
    }
}