Matrix Zigzag Traversal

Question

  1. Given a matrix of m x n elements (m rows, n columns),
  2. return all elements of the matrix in ZigZag-order.
  4. Example
  5. Given a matrix:
  7. [
  8.   [1, 2,  3,  4],
  9.   [5, 6,  7,  8],
  10.   [9,10, 11, 12]
  11. ]
  12. return [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]

题解

按之字形遍历矩阵，纯粹找下标规律。以题中所给范例为例，设(x, y)为矩阵坐标，按之字形遍历有如下规律：

  1. (0, 0)
  2. (0, 1), (1, 0)
  3. (2, 0), (1, 1), (0, 2)
  4. (0, 3), (1, 2), (2, 1)
  5. (2, 2), (1, 3)
  6. (2, 3)

可以发现其中每一行的坐标之和为常数，坐标和为奇数时 x 递增，为偶数时 x 递减。

Java - valid matrix index second

  1. public class Solution {
  2.     /**
  3.      * @param matrix: a matrix of integers
  4.      * @return: an array of integers
  5.      */
  6.     public int[] printZMatrix(int[][] matrix) {
  7.         if (matrix == null || matrix.length == 0) return null;
  9.         int m = matrix.length - 1, n = matrix[0].length - 1;
  10.         int[] result = new int[(m + 1) * (n + 1)];
  11.         int index = 0;
  12.         for (int i = 0; i <= m + n; i++) {
  13.             if (i % 2 == 0) {
  14.                 for (int x = i; x >= 0; x--) {
  15.                     // valid matrix index
  16.                     if ((x <= m) && (i - x <= n)) {
  17.                         result[index] = matrix[x][i - x];
  18.                         index++;
  19.                     }
  20.                 }
  21.             } else {
  22.                 for (int x = 0; x <= i; x++) {
  23.                     if ((x <= m) && (i - x <= n)) {
  24.                         result[index] = matrix[x][i - x];
  25.                         index++;
  26.                     }
  27.                 }
  28.             }
  29.         }
  31.         return result;
  32.     }
  33. }

Java - valid matrix index first

  1. public class Solution {
  2.     /**
  3.      * @param matrix: a matrix of integers
  4.      * @return: an array of integers
  5.      */
  6.     public int[] printZMatrix(int[][] matrix) {
  7.         if (matrix == null || matrix.length == 0) return null;
  9.         int m = matrix.length - 1, n = matrix[0].length - 1;
  10.         int[] result = new int[(m + 1) * (n + 1)];
  11.         int index = 0;
  12.         for (int i = 0; i <= m + n; i++) {
  13.             int upperBoundx = Math.min(i, m); // x <= m
  14.             int lowerBoundx = Math.max(0, i - n); // lower bound i - x(y) <= n
  15.             int upperBoundy = Math.min(i, n); // y <= n
  16.             int lowerBoundy = Math.max(0, i - m); // i - y(x) <= m
  17.             if (i % 2 == 0) {
  18.                 // column increment
  19.                 for (int y = lowerBoundy; y <= upperBoundy; y++) {
  20.                     result[index] = matrix[i - y][y];
  21.                     index++;
  22.                 }
  23.             } else {
  24.                 // row increment
  25.                 for (int x = lowerBoundx; x <= upperBoundx; x++) {
  26.                     result[index] = matrix[x][i - x];
  27.                     index++;
  28.                 }
  29.             }
  30.         }
  32.         return result;
  33.     }
  34. }

源码分析

矩阵行列和分奇偶讨论，奇数时行递增，偶数时列递增，一种是先循环再判断索引是否合法，另一种是先取的索引边界。

复杂度分析

后判断索引是否合法的实现遍历次数为 1 + 2 + … + (m + n) = O((m+n)^2), 首先确定上下界的每个元素遍历一次，时间复杂度 O(m \cdot n). 空间复杂度都是 O(1).

Reference