LeetCode Diagonal Traverse

LeetCode 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:

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

Note:

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

给定一个矩阵,要求以对角线的方式遍历该矩阵。

没什么特别的技巧,模拟对角线走法即可。设置一个up变量,设置up=true表示向右上角走,i--,j++;up=false表示向左下角走,i++,j--。

边界情况处理有点复杂。当向右上角走时,有两种情况,如果越过了右边界,比如样例中3往右上角走了一步,则要回到6的位置,方法是i+=2,j=n-1;如果没有越过右边界,只是越过了上边界,比如图中的1再往右上角走了一步,则只需要i=0。注意这两种判断的顺序不能乱,必须先判断是否越过了右边界,再判断是否越过了上边界。

当往左下角走时,越界处理的方法类似。如果越过了下边界,比如8再往左下角走了一步,则需要i=m-1,j+=2;如果只越过了左边界,比如4再往左下角走了一步,则只需要j=0。

完整代码如下:

class Solution {
public:
	vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
		int m = matrix.size(), n = 0;
		if (m != 0)n = matrix[0].size();
		if (m == 0 || n == 0)return vector<int>();
		vector<int> ans;
		int i = 0, j = 0;
		bool up = true;
		while (!(i == m - 1 && j == n - 1)) {
			ans.push_back(matrix[i][j]);
			if (up) {
				--i;
				++j;
				if (j >= n) {
					i += 2;
					j = n - 1;
					up = false;
				}
				if (i < 0) {
					i = 0;
					up = false;
				}
			}
			else {
				++i;
				--j;
				if (i >= m) {
					i = m - 1;
					j += 2;
					up = true;
				}
				if (j < 0) {
					j = 0;
					up = true;
				}

			}
		}
		ans.push_back(matrix[m - 1][n - 1]);
		return ans;
	}
};

本代码提交AC,用时86MS。

Leave a Reply

Your email address will not be published. Required fields are marked *