题目描述

题目：

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

示例:

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

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

说明:给定矩阵中的元素总数不会超过 100000 。

解题思路

我们发现:

1. 对角线遍历的次数为M+N-1,如上图3x3的矩阵遍历了3+3-1 = 5次对角线
2. 对角线上的行列坐标之和等于对角线遍历的次序(从0开始计数),如第一次遍历行列坐标为0,
   第二次遍历行列坐标为1.
3. 当对角线遍历次序为偶数是向斜上遍历,当对角线遍历次序为奇数时向斜下遍历 如一次遍历(次序为0)向斜上遍历,第二次遍历(次序为1)向斜下遍历
4. 当对角线遍历触碰到边界时会转换方向:
   i.向斜上方遍历会触碰到的边界有两种情况
   -----1)在没过主对角线之前向斜上方遍历只会触碰到矩阵上边界(即row == 0);
   -----2)在过主对角线之后向斜上方遍历只会触碰到矩阵右边界(即col == N-1);
   
   ii.向斜下方遍历会触碰到的边界有两种情况
   -----1)在没过主对角线之前向斜下方遍历只会触碰到矩阵左边界(即col == 0);
   -----2)在过主对角线之后向斜下方遍历只会触碰到矩阵下边界(即row == M-1);
   

代码演示

int* findDiagonalOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
    if(matrixSize==0){
        *returnSize=0;
        return 0;
    }
    int row=0,column=0,k=0;
    *returnSize=matrixSize*(*matrixColSize);
    int* res=malloc(*returnSize * sizeof(int));
    while(k<*returnSize){
        res[k]=matrix[row][column];
        if((row+column)%2){//对角线遍历次序奇数时
            if(row==matrixSize-1) column++;//斜向下遍历碰到下边界时
            else{
                row++;
                if(column) column--;//斜向上遍历没有碰到左边界时,正常斜向下移动如果碰到边界只会向下移动一个位置,使遍历次序变成偶数,即方向转换
            }
        } else {//对角线遍历次序为偶数时
            if(column==*matrixColSize-1) row++;//斜向上遍历碰到右边界时
            else{
                column++;
                if(row) row--;//斜向上遍历没有碰到上边界时
            }
        }
        k++;
    }
    return res;
}