题目

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:

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

Explanation:

image.png

Note:

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

题意

按照对角线方向遍历矩阵。

思路

可以按照图示路线进行模拟，或者直接每次都按照右上到左下的顺序遍历，并把奇数次的遍历翻转过来：
image.png

代码实现

Java

模拟

  1. class Solution {
  2.     public int[] findDiagonalOrder(int[][] matrix) {
  3.         if (matrix.length == 0) {
  4.             return new int[0];
  5.         }
  7.         int m = matrix.length, n = matrix[0].length;
  8.         int[] ans = new int[m * n];
  9.         int x = 0, y = 0;
  10.         int xStep = -1, yStep = 1;
  12.         for (int i = 0; i < m * n; i++) {
  13.             ans[i] = matrix[x][y];
  14.             int nextX = x + xStep, nextY = y + yStep;
  16.             if (nextX == -1 && nextY == n) {
  17.                   // 当前在右上角，且要继续向右上走
  18.                 x = x + 1;
  19.             } else if (nextX == -1 || nextY == n) {
  20.                   // 当前在上边界或右边界，且要继续向右上走
  21.                 x = nextX == -1 ? x : x + 1;
  22.                 y = nextY == n ? y : y + 1;
  23.             } else if (nextX == m && nextY == -1) {
  24.                   // 当前在左下角，且要继续向左下走
  25.                 y = y + 1;
  26.             } else if (nextX == m || nextY == -1) {
  27.                   // 当前在左边界或下边界，且要继续向左下走
  28.                 x = nextX == m ? x : x + 1;
  29.                 y = nextY == -1 ? y : y + 1;
  30.             } else {
  31.                 x = nextX;
  32.                 y = nextY;
  33.             }
  35.             if (nextX == -1 || nextY == -1 || nextX == m || nextY == n) {
  36.                 xStep = -xStep;
  37.                 yStep = -yStep;
  38.             }
  39.         }
  41.         return ans;
  42.     }
  43. }

翻转

  1. class Solution {
  2.     public int[] findDiagonalOrder(int[][] matrix) {
  3.         if (matrix.length == 0) {
  4.             return new int[0];
  5.         }
  7.         int m = matrix.length, n = matrix[0].length;
  8.         int[] ans = new int[m * n];
  9.         int index = 0;
  11.         for (int i = 0; i < m + n - 1; i++) {
  12.             int x = i < n ? 0 : i - n + 1, y = i < n ? i : n - 1;
  13.             int start = index;
  14.             while (x < m && y >= 0) {
  15.                 ans[index++] = matrix[x++][y--];
  16.             }
  17.             if (i % 2 == 0) {
  18.                 reverse(ans, start, index - 1);
  19.             }
  20.         }
  22.         return ans;
  23.     }
  25.     private void reverse(int[] A, int start, int end) {
  26.         while (start < end) {
  27.             int tmp = A[start];
  28.             A[start++] = A[end];
  29.             A[end--] = tmp;
  30.         }
  31.     }
  32. }