【leetcode】4. 数组-对角线遍历

题目

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

示例:

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

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

解释:

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

题解

分析

本题需要仔细揣摩题目，找出规律。抓住两点：

1. 题目实例，如果给出的3*3的矩阵不能有所收获的话，可以尝试更其他组合的矩阵，比如4*3等等。
2. 题图，图的表现力更强一些，同样，如果题目种的图不能发现规律的话，可以尝试更多的矩阵。
   经过一通分析，发现如下规律[为表述方便设某一元素的坐标为(x,y)]：
3. x + y 为偶数是遍历方向为：左下->右上，x--，y++，x + y 为奇数是遍历方向为：右上->左下,y--, x++
4. 一共遍历M + N - 1 次，即遍历[0, M+N-2]
5. 第n次遍历是n = x + y，n从0开始
6. 每次遍历的时候，左下->右上 若x < M则起点为(n, 0)否则为(M-1,n-M-1);右上->左下若y < N则起点为(0, n)否则为(n-N-1, N-1)

具体分析如下(以示例种3*3矩阵举例)：
第0趟 x = 0, y = 0; x + y = 0，0是偶数，左下->右上，[(0,0)],[1]
第1趟 x = 0, y = 1; x + y = 1，1是奇数，右上->左下，[(0,1),(1,0)],[2,4]
第2趟 x = 2, y = 0; x + y = 2，2是偶数，左下->右上，[(2,0),(1,1),(0,2)],[7,5,3]
第3趟 x = 1, y = 2; x + y = 3，3是奇数，右上->左下，[(1,2),(2,1)],[6,8]
第4趟 x = 2, y = 2; x + y = 4，4是偶数，左下->右上，[(2,2)],[9]
因此，对角遍历后的结果为[1,2,4,7,5,3,6,8,9]

时间复杂度：O(N*N)
空间复杂度：O(N)

代码

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> ret;
        int m = matrix.size();
        if (m == 0) {
            return ret;
        }
        int n = matrix[0].size();
        for (int t = 0; t < m + n; t++) {
            int x = 0, y = 0;
            if (t % 2 == 0) {
                x = t < m ? t : m - 1;
                y = t - x;
                while (x >= 0 && y < n) {
                    ret.push_back(matrix[x][y]);
                    x--;
                    y++;
                }
            } else {
                y = t < n ? t : n - 1;
                x = t - y;
                while (y >= 0 && x < m) {
                    ret.push_back(matrix[x][y]);
                    y--;
                    x++;
                }
            }
        }
        return ret;
    }
};