LeetCode 498. Diagonal Traverse

498. Diagonal Traverse

Total Accepted: 2819
Total Submissions: 6146
Difficulty: Medium
Contributors: nberserk

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.

Subscribe to see which companies asked this question.

【题目分析】

给定一个M行N列矩阵，用对角顺序返回矩阵的所有元素。

【思路】

初始对角线方向为右上方（偏移量：行-1, 列+1），遇到边界时转向左下方（偏移量：行+1, 列-1）

If out of bottom border (row >= m) then row = m - 1; col += 2; change walk direction.
if out of right border (col >= n) then col = n - 1; row += 2; change walk direction.
if out of top border (row < 0) then row = 0; change walk direction.
if out of left border (col < 0) then col = 0; change walk direction.
Otherwise, just go along with the current direction.

【java代码】

 1 public class Solution {
 2     public int[] findDiagonalOrder(int[][] matrix) {
 3         int row = matrix.length;
 4         if(row == 0) return new int[0];
 5         
 6         int col = matrix[0].length;
 7         int[] res = new int[row*col];
 8         
 9         int m = 0, n = 0, d = 1;
10         for(int i = 0; i < row*col; i++) {
11             res[i] = matrix[m][n];
12             m -= d;
13             n += d;
14             if(m >= row) {m = row - 1; n += 2; d = -d;}
15             if(n >= col) {n = col - 1; m += 2; d = -d;}
16             if(m < 0) {m = 0; d = -d;}
17             if(n < 0) {n = 0; d = -d;}
18         }
19         
20         return res;
21     }
22 }