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:
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.
[Thoughts]
以题中示例为例子,看一下坐标的变化,如下图
在上升通道的时候, row = row -1, col = col +1
在下降通道的时候,row = row +1, col = col -1
当坐标变化超出数组范围的时候,要遵循以下原则调整:
1. 如果row < 0, row = 0, 变换通道
2. 如果col < 0, col = 0, 变换通道
3. 如果 col > N, col = N-1, row = row +2;
4. 如果 row > M, row = M-1. col = col +2;
[Code]
1: vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
2: if(matrix.size() == 0 || matrix[0].size() == 0) return {};
3:
4: vector<int> result;
5:
6: vector<pair<int, int>> move_delta{{-1, 1}, {1, -1}};
7:
8: int rows = matrix.size(), cols = matrix[0].size();
9: int row = 0, col = 0, m = 0;
10: for(int i = 0; i< rows * cols; i++) {
11: result.push_back(matrix[row][col]);
12: row += move_delta[m].first;
13: col += move_delta[m].second;
14:
15: if(row >= rows) {
16: row = rows-1;
17: col = col +2;
18: m = 1-m;
19: }
20:
21: if(col >= cols) {
22: col = cols -1;
23: row = row + 2;
24: m = 1-m;
25: }
26:
27: if(row < 0) {
28: row = 0;
29: m = 1-m;
30: }
31:
32: if(col < 0) {
33: col = 0;
34: m = 1-m;
35: }
36: }
37: return result;
38: }
No comments:
Post a Comment