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:

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

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

Explanation:

Note:

The total number of elements of the given matrix will not exceed 10,000.


LC in C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
if(matrix.empty()) return {};

const int N = matrix.size();
const int M = matrix[0].size();

vector<int> res;
for(int s = 0; s <= N + M - 2; ++s)//1.
{
// for all i + j = s
for(int x = 0; x <= s; ++x)
{
int i = x;
int j = s - i;
if(s % 2 == 0) swap(i, j);//2.inner loop每次都是(0,s)开始的,但是偶数对角线是(s,0)开始的,所以要交换
if(i >= N || j >= M) continue;//3.
res.push_back(matrix[i][j]);
}
}
return res;
}

细节

  1. i+j = diaindex (diagonal number - 1)对角线的坐标和,等于,对角线的索引
    1. maxdiaindex = ((N-1) + (M-1)) = N + M - 2
  2. iterate through all diaindex (denote this as s )
    1. find pairs (i, j) : i + j = s .
    2. the order :
      1. even start : (s, 0),swap (i,j)
      2. odd start:(0, s)
  3. 边界控制,越界continue

总结

  1. 主要是对角线索引== 坐标索引之和,跟矩阵内部的数 一点关系都没有,从坐标下手
  2. 知道row就可以推断出col=s-row。
  3. 顺序的话,因为row++,每次都是(0,s)开始的。按题意,如果s是even,就swap(i,j)
  4. 另外注意每次iteration的时候,越界跳出,continue
Thanks for Support.