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)，只使用了常數個額外變量。

這種打印方式在實際應用中可能用于特殊的數據展示需求，或者作為某些圖像處理算法的預處理步驟。理解這種遍歷方式有助于加深對矩陣操作的理解。