Massive Algorithms: LintCode 185 - matrix zigzag traversal

LeetCode 498 - Diagonal Traverse
http://lintcode.peqiu.com/content/lintcode/matrix_zigzag_traversal.html

lintcode: (185) 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 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 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)

, 首先确定上下界的每个元素遍历一次，时间复杂度

O(m \cdot n)

. 空间复杂度都是

O(1)

http://cherylintcode.blogspot.com/2015/07/matrix-zigzag-traversal.html
public int[] printZMatrix(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return null;
int m = matrix.length, n = matrix[0].length;
int[] res = new int[m*n];
int j = 0;
for(int i = 0; i < m + n - 1; i++){
if(i % 2 == 1){
for(int y = Math.min(i, n - 1); y >= Math.max(0, i - m + 1); y--){
res[j++] = matrix[i-y][y];
}
} else{
for(int x = Math.min(i, m - 1); x >= Math.max(0, i - n + 1); x--){
res[j++] = matrix[x][i-x];
}
}
}
return res;
}
http://blog.csdn.net/wutingyehe/article/details/46629087

public int[] printZMatrix(int[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return null; int count = matrix.length * matrix[0].length; int[] array = new int[count]; int r = 0, c = 0; array[0] = matrix[0][0]; for (int i = 1; i < count; ) { //斜上走到顶 while(i < count && r - 1 >= 0 && c + 1 < matrix[0].length) { array[i++] = matrix[--r][++c]; } //横右走一步，不可横右走时竖下走一步 if (i < count && c + 1 < matrix[0].length) { array[i++] = matrix[r][++c]; } else if (i < count && r + 1 < matrix.length) { array[i++] = matrix[++r][c]; } //斜下走到底 while(i < count && r + 1 < matrix.length && c - 1 >= 0) { array[i++] = matrix[++r][--c]; } //竖下走一步，不可竖下走时横右走一步 if (i < count && r + 1 < matrix.length) { array[i++] = matrix[++r][c]; } else if (i < count && c + 1 < matrix[0].length) { array[i++] = matrix[r][++c]; } } return array; }

Related:
http://rosettacode.org/wiki/Zig-zag_matrix#Java

public static int[][] Zig_Zag(final int size)
{
 int[][] data = new int[size][size];
 int i = 1;
 int j = 1;
 for (int element = 0; element < size * size; element++)
 {
  data[i - 1][j - 1] = element;
  if ((i + j) % 2 == 0)
  {
   // Even stripes
   if (j < size)
    j++;
   else
    i+= 2;
   if (i > 1)
    i--;
  }
  else
  {
   // Odd stripes
   if (i < size)
    i++;
   else
    j+= 2;
   if (j > 1)
    j--;
  }
 }
 return data;
}

http://www.cnblogs.com/EdwardLiu/p/6359701.html

 7     static void print(int rows, int cols) {
 8         int limit = rows * cols;
 9         int T = rows * 2; // cycle
10         for (int i=1; i<=rows; i++) {
11             int[] curRow = new int[cols];
12             int k = 0;
13             int index = 0;
14             while (k * T + i <= limit || k * T + T - i + 1 <= limit) {
15                 if (k * T + i <= limit) curRow[index++] = k * T + i;
16                 if (k * T + T - i + 1 <= limit) curRow[index++] = k * T + T - i + 1;
17                 k++;
18             }
19             System.out.println(Arrays.toString(curRow));
20         }
21         
22     }

LintCode 185 - matrix zigzag traversal

题解

后判断索引是否合法的实现遍历次数为

Labels

Popular Posts