interviewalgo
, ,
Source
Edit
History

498. 对角线遍历

Introduction

Question: 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 。

解法一

Analysis

这道题还是看之前写的博客才AC的，简单来讲就是要找到一个规律：

  • 边界时，只有向右移动和向下移动两种情况
  • 在向右上移动时遇到边界，优先向右移动
  • 在向左下移动时遇到边界，优先向左移动

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
    vector<int> res;
    int m = matrix.size();
    if (m == 0) return res;
    int n = matrix[0].size();

    int i = 0,j = 0;
    int state = 0;
    int nextI[2] = {-1, 1};
    int nextJ[2] = {1, -1};

    auto right = [n](int &j) {
        bool res = j + 1 < n;
        j += res;
        return res;
    };
    auto down = [m](int &i) {
        bool res = i + 1 < m;
        i += res;
        return res;
    };

    for(int t = 0, size = m * n; t < size; t++) {
        res.push_back(matrix[i][j]);
        i += nextI[state];
        j += nextJ[state];
        if (i < 0 || j < 0 || i == m || j == n) {
            i -= nextI[state];
            j -= nextJ[state];

            if (state == 0) {
                right(j) || down(i);
            } else {
                down(i) || right(j);
            }

            state = !state;
        }
    }

    return res;
}