498. Diagonal Traverse

  • 45.8%

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.

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

Explanation:
image

Note:

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


方法一:

https://discuss.leetcode.com/topic/77918/c-without-paying-too-much-attention-on-direction-switch

Put all diagonal sequences from top-right to bottom-left to an array and then combine all sequence together by reversing odd sequences.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m == 0) return vector<int>();
int n = matrix[0].size();
vector<vector<int>> tmp (m+n-1);
for (int i = 0; i < m+n-1 ; i++) {
int row = max(0, i-n+1);
int col = min(i, n-1);
for (; col >= 0 && row < m; row++, col--) {
tmp[i].push_back(matrix[row][col]);
}
}
vector<int> res;
for (int i = 0; i< tmp.size(); i++) {
if (i % 2) res.insert(res.end(), tmp[i].begin(), tmp[i].end());
else res.insert(res.end(), tmp[i].rbegin(), tmp[i].rend());
}
return res;
}
};

Some simple modification eliminates the use of a temporary storage.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {

if (matrix.size() == 0 || matrix[0].size() == 0) return {};
int m = matrix.size(), n = matrix[0].size();

vector<int> res;
for (int i = 0; i < m+n-1; i++) {
int begin_pos = res.size();
for (int row = max(0, i-n+1), col = min(i, n-1); col >= 0 && row < m; row++, col--)
res.push_back(matrix[row][col]);
if (i % 2 == 0) reverse(res.begin() + begin_pos, res.end());
}

return res;
}
谢谢你,可爱的朋友。