Diagonal Traverse (M)
题目
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.
题意
按照对角线方向遍历矩阵。
思路
可以按照图示路线进行模拟,或者直接每次都按照右上到左下的顺序遍历,并把奇数次的遍历翻转过来:
代码实现
Java
模拟
class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix.length == 0) {
return new int[0];
}
int m = matrix.length, n = matrix[0].length;
int[] ans = new int[m * n];
int x = 0, y = 0;
int xStep = -1, yStep = 1;
for (int i = 0; i < m * n; i++) {
ans[i] = matrix[x][y];
int nextX = x + xStep, nextY = y + yStep;
if (nextX == -1 && nextY == n) {
// 当前在右上角,且要继续向右上走
x = x + 1;
} else if (nextX == -1 || nextY == n) {
// 当前在上边界或右边界,且要继续向右上走
x = nextX == -1 ? x : x + 1;
y = nextY == n ? y : y + 1;
} else if (nextX == m && nextY == -1) {
// 当前在左下角,且要继续向左下走
y = y + 1;
} else if (nextX == m || nextY == -1) {
// 当前在左边界或下边界,且要继续向左下走
x = nextX == m ? x : x + 1;
y = nextY == -1 ? y : y + 1;
} else {
x = nextX;
y = nextY;
}
if (nextX == -1 || nextY == -1 || nextX == m || nextY == n) {
xStep = -xStep;
yStep = -yStep;
}
}
return ans;
}
}
翻转
class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix.length == 0) {
return new int[0];
}
int m = matrix.length, n = matrix[0].length;
int[] ans = new int[m * n];
int index = 0;
for (int i = 0; i < m + n - 1; i++) {
int x = i < n ? 0 : i - n + 1, y = i < n ? i : n - 1;
int start = index;
while (x < m && y >= 0) {
ans[index++] = matrix[x++][y--];
}
if (i % 2 == 0) {
reverse(ans, start, index - 1);
}
}
return ans;
}
private void reverse(int[] A, int start, int end) {
while (start < end) {
int tmp = A[start];
A[start++] = A[end];
A[end--] = tmp;
}
}
}