⭐ 题目日期：

B 站 - 2024/11/26

🌳 题目描述：

对一个 n × n 的矩阵进行 Z 字形遍历，要求按照对角线顺序输出元素。

🕵🏽面试评估：

这道题主要考察候选人能否识别对角线的扫描逻辑(行号和列号之和等于对角线编号), 再根据对角线编号的奇偶性决定遍历方向。

🧗难度系数：

⭐️ ⭐️ ⭐

📝思路分析：

以 4 X 4 的矩阵为例，左上角的 1 和右下角的 16 的线性扫描是它们本身。因此我们可以统一矩阵的遍历路线，得到：

观察以上遍历路线，我们发现：

1. 一共有 2 * n - 1 条对角线，可以分别编号 0， 1， 2 ... 2n - 2；
2. 偶数编号 i 的对角线都是从左下到右上，元素索引记为 (row, col), 该类对角线总是从 col = 0 开始遍历, col 逐渐变大，且满足 row + col = i；
3. 奇数编号 i 的对角线都是从右上到左下，元素索引记为 (row, col), 该类对角线总是从 row = 0 开始遍历，并且 row 逐渐变大, 且满足 row + col = i；

观察到以上规律，代码从对角线入手，按顺序遍历所有对角线，如果对角线为偶数，从 0 到 i 遍历 col, 与此同时也能计算出 row (row = i - col); 如果对角线为奇数，从 0 到 i 遍历 row, 与此同时也能计算出 col (col = i - row)。重复以上过程，直到所有对角线都被访问。

💻代码：

Java

public List<Integer> zigzagScan(int[][] matrix) {
    int n = matrix.length;
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i <= 2 * (n - 1); i++) {
        // 遍历每条对角线
        for (int j = 0; j <= i; j++) {
            if (j < n && i - j < n) {
                result.add(i % 2 == 0 ? matrix[i - j][j] : matrix[j][i - j]);
            }
        }
    }

    return result;
}

Python

def zigzag_scan(matrix):
    n = len(matrix)
    result = []

    for i in range(2 * n - 1):
        # 遍历每条对角线
        for j in range(i + 1):
            if j < n and i - j < n:
                if i % 2 == 0:
                    result.append(matrix[i - j][j])
                else:
                    result.append(matrix[j][i - j])

    return result

C++

#include <iostream>
#include <vector>

using namespace std; 

public:
vector<int> zigzag_scan(const vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<int> result;

    for (int i = 0; i < 2 * n - 1; i++) {
        // 遍历每条对角线
        for (int j = 0; j <= i; j++) {
            if (j < n && i - j < n) {
                if (i % 2 == 0) {
                    result.push_back(matrix[i - j][j]);
                } else {
                    result.push_back(matrix[j][i - j]);
                }
            }
        }
    }

    return result;
}

🚵🏻复杂度分析：

n x n 的矩阵

时间复杂度：O(n^2)，n x n 矩阵一共有 n^2 个元素，每个元素都遍历一遍

空间复杂度：O(n^2)，需要存储 n^2 个元素