左神算法之Zigzag方式打印矩阵

Zigzag方式打印矩阵

1. 题目

用zigzag的方式打印矩阵，比如下面的矩阵：

0 1 2 3
4 5 6 7 
8 9 10 11

打印顺序为：0 1 4 8 5 2 3 6 9 10 7 11

2. 解释

Zigzag打印矩阵是指按照对角线交替方向打印矩阵元素。具体来说：

1. 从左上角(0,0)开始，向右移动
2. 当到达第一行末尾时，向下移动
3. 然后按照左下到右上的方向打印对角线
4. 接着按照右上到左下的方向打印对角线
5. 如此交替，直到打印完所有元素

对于示例矩阵，打印顺序如下：

• 向右：0
• 向右：1
• 左下到右上：4→1 (但1已打印)，实际是4
• 右下到左下：8→5→2
• 右上到左下：3 (已到达右边界，向下)
• 左下到右上：6→9
• 右上到左下：10→7
• 左下到右上：11

3. 思路

我们可以使用两个变量来追踪当前打印的对角线的起点，并交替改变打印方向：

1. 初始化两个点A和B，都从(0,0)开始
2. A点先向右移动，到达右边界后向下移动
3. B点先向下移动，到达下边界后向右移动
4. 每次A和B确定一条对角线，交替方向打印这条对角线上的元素
5. 直到A和B都到达矩阵右下角结束

4. 代码

public class ZigzagPrintMatrix {public static void printMatrixZigzag(int[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return;}int aR = 0, aC = 0;  // A点的行和列int bR = 0, bC = 0;   // B点的行和列int endR = matrix.length - 1;int endC = matrix[0].length - 1;boolean fromUp = false; // 打印方向标志，false表示从下往上while (aR != endR + 1) {printDiagonal(matrix, aR, aC, bR, bC, fromUp);// 更新A点：先向右，到达右边界后向下aR = aC == endC ? aR + 1 : aR;aC = aC == endC ? aC : aC + 1;// 更新B点：先向下，到达下边界后向右bC = bR == endR ? bC + 1 : bC;bR = bR == endR ? bR : bR + 1;fromUp = !fromUp; // 切换打印方向}System.out.println();}private static void printDiagonal(int[][] matrix, int aR, int aC, int bR, int bC, boolean fromUp) {if (fromUp) {// 从右上到左下打印while (aR <= bR) {System.out.print(matrix[aR++][aC--] + " ");}} else {// 从左下到右上打印while (bR >= aR) {System.out.print(matrix[bR--][bC++] + " ");}}}public static void main(String[] args) {int[][] matrix = {{0, 1, 2, 3},{4, 5, 6, 7},{8, 9, 10, 11}};printMatrixZigzag(matrix); // 输出: 0 1 4 8 5 2 3 6 9 10 7 11 }
}

5. 总结

Zigzag打印矩阵的关键在于：

1. 确定两个移动点A和B的移动规律
2. 交替改变对角线的打印方向
3. 正确处理边界条件

这种方法的时间复杂度是O(M×N)，其中M和N分别是矩阵的行数和列数，因为我们只访问每个元素一次。空间复杂度是O(1)，只使用了常数个额外变量。

这种打印方式在实际应用中可能用于特殊的数据展示需求，或者作为某些图像处理算法的预处理步骤。理解这种遍历方式有助于加深对矩阵操作的理解。