左神算法之Zigzag方式打印矩阵
目录
- Zigzag方式打印矩阵
- 1. 题目
- 2. 解释
- 3. 思路
- 4. 代码
- 5. 总结
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打印矩阵是指按照对角线交替方向打印矩阵元素。具体来说：
- 从左上角(0,0)开始，向右移动
- 当到达第一行末尾时，向下移动
- 然后按照左下到右上的方向打印对角线
- 接着按照右上到左下的方向打印对角线
- 如此交替，直到打印完所有元素
对于示例矩阵，打印顺序如下：
- 向右：0
- 向右：1
- 左下到右上：4→1 (但1已打印)，实际是4
- 右下到左下：8→5→2
- 右上到左下：3 (已到达右边界，向下)
- 左下到右上：6→9
- 右上到左下：10→7
- 左下到右上：11
3. 思路
我们可以使用两个变量来追踪当前打印的对角线的起点，并交替改变打印方向：
- 初始化两个点A和B，都从(0,0)开始
- A点先向右移动，到达右边界后向下移动
- B点先向下移动，到达下边界后向右移动
- 每次A和B确定一条对角线，交替方向打印这条对角线上的元素
- 直到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打印矩阵的关键在于：
- 确定两个移动点A和B的移动规律
- 交替改变对角线的打印方向
- 正确处理边界条件
这种方法的时间复杂度是O(M×N)，其中M和N分别是矩阵的行数和列数，因为我们只访问每个元素一次。空间复杂度是O(1)，只使用了常数个额外变量。
这种打印方式在实际应用中可能用于特殊的数据展示需求，或者作为某些图像处理算法的预处理步骤。理解这种遍历方式有助于加深对矩阵操作的理解。