# Matrix Zigzag Traversal ### Source - lintcode: [(185) Matrix Zigzag Traversal](http://www.lintcode.com/en/problem/matrix-zigzag-traversal/) ~~~ Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in ZigZag-order. Example Given a matrix: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10, 11, 12] ] return [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12] ~~~ ### 題解 按之字形遍歷矩陣，純粹找下標規律。以題中所給范例為例，設`(x, y)`為矩陣坐標，按之字形遍歷有如下規律： ~~~ (0, 0) (0, 1), (1, 0) (2, 0), (1, 1), (0, 2) (0, 3), (1, 2), (2, 1) (2, 2), (1, 3) (2, 3) ~~~ 可以發現其中每一行的坐標之和為常數，坐標和為奇數時 x 遞增，為偶數時 x 遞減。 ### Java - valid matrix index second ~~~ public class Solution { /** * @param matrix: a matrix of integers * @return: an array of integers */ public int[] printZMatrix(int[][] matrix) { if (matrix == null || matrix.length == 0) return null; int m = matrix.length - 1, n = matrix[0].length - 1; int[] result = new int[(m + 1) * (n + 1)]; int index = 0; for (int i = 0; i <= m + n; i++) { if (i % 2 == 0) { for (int x = i; x >= 0; x--) { // valid matrix index if ((x <= m) && (i - x <= n)) { result[index] = matrix[x][i - x]; index++; } } } else { for (int x = 0; x <= i; x++) { if ((x <= m) && (i - x <= n)) { result[index] = matrix[x][i - x]; index++; } } } } return result; } } ~~~ ### Java - valid matrix index first ~~~ public class Solution { /** * @param matrix: a matrix of integers * @return: an array of integers */ public int[] printZMatrix(int[][] matrix) { if (matrix == null || matrix.length == 0) return null; int m = matrix.length - 1, n = matrix[0].length - 1; int[] result = new int[(m + 1) * (n + 1)]; int index = 0; for (int i = 0; i <= m + n; i++) { int upperBoundx = Math.min(i, m); // x <= m int lowerBoundx = Math.max(0, i - n); // lower bound i - x(y) <= n int upperBoundy = Math.min(i, n); // y <= n int lowerBoundy = Math.max(0, i - m); // i - y(x) <= m if (i % 2 == 0) { // column increment for (int y = lowerBoundy; y <= upperBoundy; y++) { result[index] = matrix[i - y][y]; index++; } } else { // row increment for (int x = lowerBoundx; x <= upperBoundx; x++) { result[index] = matrix[x][i - x]; index++; } } } return result; } } ~~~ ### 源碼分析 矩陣行列和分奇偶討論，奇數時行遞增，偶數時列遞增，一種是先循環再判斷索引是否合法，另一種是先取的索引邊界。 ### 復雜度分析 后判斷索引是否合法的實現遍歷次數為 1+2+...+(m+n)=O((m+n)2)1 + 2 + ... + (m + n) = O((m+n)^2)1+2+...+(m+n)=O((m+n)2), 首先確定上下界的每個元素遍歷一次，時間復雜度 O(m?n)O(m \cdot n)O(m?n). 空間復雜度都是 O(1)O(1)O(1). ### Reference - [LintCode/matrix-zigzag-traversal.cpp at master · kamyu104/LintCode](https://github.com/kamyu104/LintCode/blob/master/C++/matrix-zigzag-traversal.cpp)