之字形打印矩阵

题目

给定一个矩阵, 按照之字型的方式打印矩阵, 例如

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

输出

1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12

要求

额外空间复杂度为 O(1)

题解

本题可以考虑设定两个游标 a 和 b , 初始时均指向左上角, 后分别沿上边界和左边界移动, 当运动到边的末尾时分别向下和向右移动, 打印 a 和 b 两点形成的对角线上的点即可.

需注意 a, b 横纵坐标增加的顺序, 否则容易在拐点出现下标越界

图来自程序员客栈

Java

public class PrintMatrixZigZag {
    public static void printMatrixZigZag(int[][] matrix) {
        int row1 = 0;
        int col1 = 0;
        int row2 = 0;
        int col2 = 0;
        int endR = matrix.length - 1;
        int endC = matrix[0].length - 1;
        boolean fromUp = false;
        while (row1 <= endR) {
            printDiagonal(matrix, row1, col1, row2, col2, fromUp);
            // 需注意 a, b 横纵坐标增加的顺序, 否则容易在拐点出现下标越界
            row1 = col1 == endC ? row1 + 1 : row1;
            col1 = col1 == endC ? col1 : col1 + 1;
            col2 = row2 == endR ? col2 + 1 : col2;
            row2 = row2 == endR ? row2 : row2 + 1;
            fromUp = !fromUp; // 反转
        }
    }

    /**
     * @param fromUp True: 从上向下打印
     */
    public static void printDiagonal(int[][] m, int row1, int col1, int row2, int col2, boolean fromUp) {
        if (fromUp) {
            while (row1 <= row2) {
                System.out.print(m[row1++][col1--] + " ");
            }
        } else {
            while (row1 <= row2) {
                System.out.print(m[row2--][col2++] + " ");
            }
        }
    }

    public static void main(String[] args) {
        int[][] inputMatrix = {
                {1, 2,  3,  4},
                {5, 6,  7,  8},
                {9, 10, 11, 12}
        };

        printMatrixZigZag(inputMatrix);
    }
}

Python

def print_matrix_zigzag(matrix):
    row1 = 0
    col1 = 0
    row2 = 0
    col2 = 0
    end_row = len(matrix) - 1
    end_col = len(matrix[0]) - 1
    from_up = False
    result = []

    while row1 <= end_row:
        result.extend(get_diagonal(matrix, row1, col1, row2, col2, from_up))
        row1 = row1 + 1 if col1 == end_col else row1
        col1 = col1 if col1 == end_col else col1 + 1
        col2 = col2 + 1 if row2 == end_row else col2
        row2 = row2 if row2 == end_row else row2 + 1
        from_up = not from_up

    print(result)


def get_diagonal(m, row1, col1, row2, col2, from_up):
    tmp_result = []
    if from_up:
        for i in range(row1, row2 + 1):
            tmp_result.append(m[i][col1])
            col1 -= 1
    else:
        for i in range(row2, row1 - 1, -1):
            tmp_result.append(m[i][col2])
            col2 += 1

    return tmp_result


if __name__ == '__main__':
    input_matrix = [
        [1, 2,  3,  4],
        [5, 6,  7,  8],
        [9, 10, 11, 12]
    ]

    print_matrix_zigzag(input_matrix)