leetcode498-Diagonal-Traverse

题目要求

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

 

Example:

Input:
[[ 1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]
]

Output:  [1,2,4,7,5,3,6,8,9]

思路和代码

其实这道题目不难，只要捋清楚一些边界的场景即可。自上而下遍历数组时，一定是自右往左移动的，因此下标移动的方向为 [row, column]=>[row+1, column-1]。自上而下有两种边界场景，一个是到达了左边界，此时的移动方向变为 [row, column]=>[row+1, column], 即上图中的 4 ->7。另一个是遇到了下边界，此时的移动方向变为 [row, column]=>[row, column+1]，即上图中的 8 ->9。同理，自下而上遍历数组时，一定是自左往右移动的，因此下标的移动方向为 [row, column]=>[row-1, column+1]。它同样有两个边界场景，一个是到达了右边界，此时的移动方向变为 [row, column]=>[row+1, column]，还有一个场景是遇到上边界，此时的移动方向变为 [row, column]=>[row, column+1]。

上述思路的代码如下：

    public int[] findDiagonalOrder(int[][] matrix) {if(matrix==null || matrix.length==0 || matrix[0].length==0) return new int[0];
        int row = matrix.length;
        int column = matrix[0].length;
        int[] result = new int[row * column];
        int rowIndex = 0;
        int columnIndex = 0;
        boolean up = true;
        int index = 0;
        while(index < result.length) {result[index++] = matrix[rowIndex][columnIndex];
            if(up) {if(rowIndex > 0 && columnIndex < column-1) {
                    rowIndex--;
                    columnIndex++;
                }else {
                    up = false;
                    if(columnIndex < column-1){columnIndex++;}else {rowIndex++;}
                }
                    
            }else {if(rowIndex < row-1 && columnIndex > 0) {
                    rowIndex++;
                    columnIndex--;
                }else{
                    up = true;
                    if(rowIndex < row-1) {rowIndex++;}else {columnIndex++;}
                }
            }
        }
        return result;
    }