498. 对角线遍历


2019-02-13 14:57:37 by Sikoay with 0 comments 1 Hits
Blog 1

代码比较臃肿,可以重构,将相同的地方提出来,就先这样吧....

问题:

498. 对角线遍历

给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。

 

示例:

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

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

解释:

 

说明:

  1. 给定矩阵中的元素总数不会超过 100000 。

 

解答:

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        int height = matrix.length;
        if(height==0)
            return new int[0];
        
        int width = matrix[0].length;
        int[] result = new int[width*height];
        int index = 0;
        
        int x =0;
        int y =0;

        boolean upper = true;

        // 第一行
        result[index] = matrix[0][0];
        upper=false;            // 第一行之后反向
        index++;
        while(true){
            // 下一列
            if(upper){
                if(x+1<height){
                    result[index] = matrix[++x][y];
                }else{
                    if(y+1<width){
                        result[index] = matrix[x][++y];
                    }else{
                        break;
                    }
                }
            }else{
                if(y+1<width){
                    result[index] = matrix[x][++y];
                }else{
                    if(x+1<height){
                        result[index] = matrix[++x][y];
                    }else{
                        break;
                    }
                }
            }
            index++;

            // 每一列中的数
            if(upper){
                while(true){
                    if(x-1>-1 && y+1<width){
                        result[index]=matrix[--x][++y];
                        index++;
                    }else{
                        break;
                    }
                }
            }else{
                while(true){
                    if(x+1<height && y-1>-1){
                        result[index]=matrix[++x][--y];
                        index++;
                    }else{
                        break;
                    }
                }
            }

            upper = upper ? false : true; // upper反向
        }

        return result;
    }
}

 

Tags:

回复 (0)

Leave a Comment