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.
A:
就是个实现题。 考的是细心不出错。
思路是这样的,每次斜着走,从右上,往左下走。然后,加入到结果里
class Solution { public: 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 r =0, c = 0; for(int r = 0, c = 0; r<m && c<n; c==n-1?r++:c++){ vector<int> V; // go to the down-left direction int rr = r, cc = c; while(rr<m && cc>=0){ if( (rr+cc)%2 == 1){ V.push_back(matrix[rr][cc]); }else{ V.insert(V.begin(), matrix[rr][cc]); } rr++; cc--; } res.insert(res.end(), V.begin(), V.end()); } return res; } };
No comments:
Post a Comment