螺旋矩阵

题目要求

编写一个函数，该函数接收一个m x n的矩阵matrix作为输入参数。你需要按照顺时针螺旋的顺序遍历矩阵，并返回一个数组，该数组依次包含矩阵中的所有元素。

解题思路

解决这个问题的关键是确定矩阵遍历的边界，并且在遍历过程中逐步缩小这些边界。以下是解题的步骤：

1. 初始化四个指标，分别代表当前遍历的上下左右边界：top（初始值为 0），bottom（初始值为 m-1），left（初始值为 0），right（初始值为 n-1）。

2. 创建一个空数组result，用于存放按顺时针螺旋顺序遍历的矩阵元素。

3. 当top小于等于bottom且left小于等于right时，执行以下步骤：

   a. 从左到右遍历上边界，即遍历top行的left到right列，遍历后top增加 1，因为上边界已经遍历过了。

   b. 从上到下遍历右边界，即遍历top到bottom行的right列，遍历后right减少 1，因为右边界已经遍历过了。

   c. 如果top仍然小于等于bottom，则从右到左遍历下边界，即遍历bottom行的right到left列，遍历后bottom减少 1，因为下边界已经遍历过了。

   d. 如果left仍然小于等于right，则从下到上遍历左边界，即遍历bottom到top行的left列，遍历后left增加 1，因为左边界已经遍历过了。

4. 重复步骤 3，直到所有的边界都已经遍历过，即top大于bottom或者left大于right。

5. 返回result数组，该数组包含了按顺时针螺旋顺序遍历的矩阵元素。

这个方法的核心在于不断地缩小遍历的范围，并且在每一步中都要检查边界条件，以确保每个元素只被访问一次。

Golang 版本

package main

import "fmt"

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return []int{}
    }

    var result []int
    top, bottom := 0, len(matrix)-1
    left, right := 0, len(matrix[0])-1

    for left <= right && top <= bottom {
        // Traverse from left to right
        for i := left; i <= right; i++ {
            result = append(result, matrix[top][i])
        }
        top++

        // Traverse downwards
        for i := top; i <= bottom; i++ {
            result = append(result, matrix[i][right])
        }
        right--

        // Make sure we are now on a different row
        if top <= bottom {
            // Traverse from right to left
            for i := right; i >= left; i-- {
                result = append(result, matrix[bottom][i])
            }
            bottom--
        }

        // Make sure we are now on a different column
        if left <= right {
            // Traverse upwards
            for i := bottom; i >= top; i-- {
                result = append(result, matrix[i][left])
            }
            left++
        }
    }

    return result
}

func main() {
    matrix := [][]int{
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9},
    }
    result := spiralOrder(matrix)
    fmt.Println(result)
}

这段代码定义了一个spiralOrder函数，它接收一个二维整数数组matrix，并返回一个一维整数数组，包含按顺时针螺旋顺序遍历的矩阵元素。main函数中给出了一个示例矩阵，并打印出了spiralOrder函数的结果。

C++版本

#include <iostream>
#include <vector>

std::vector<int> spiralOrder(const std::vector<std::vector<int>>& matrix) {
    std::vector<int> result;
    if (matrix.empty()) return result;

    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

    while (left <= right && top <= bottom) {
        // Traverse from left to right
        for (int i = left; i <= right; ++i) {
            result.push_back(matrix[top][i]);
        }
        ++top;

        // Traverse downwards
        for (int i = top; i <= bottom; ++i) {
            result.push_back(matrix[i][right]);
        }
        --right;

        if (top <= bottom) {
            // Traverse from right to left
            for (int i = right; i >= left; --i) {
                result.push_back(matrix[bottom][i]);
            }
            --bottom;
        }

        if (left <= right) {
            // Traverse upwards
            for (int i = bottom; i >= top; --i) {
                result.push_back(matrix[i][left]);
            }
            ++left;
        }
    }

    return result;
}

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    std::vector<int> result = spiralOrder(matrix);

    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

这段 C++代码定义了一个spiralOrder函数，它接收一个二维整数向量matrix作为参数，并返回一个一维整数向量，包含按顺时针螺旋顺序遍历的矩阵元素。main函数中给出了一个示例矩阵，并打印出了spiralOrder函数的结果。

Python 版本

def spiralOrder(matrix):
    if not matrix or not matrix[0]:
        return []

    result = []
    top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1

    while left <= right and top <= bottom:
        # Traverse from left to right
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1

        # Traverse downwards
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1

        if top <= bottom:
            # Traverse from right to left
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1

        if left <= right:
            # Traverse upwards
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1

    return result

# Example usage:
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

print(spiralOrder(matrix))

这段 Python 代码定义了一个spiralOrder函数，它接收一个二维列表matrix作为参数，并返回一个列表，包含按顺时针螺旋顺序遍历的矩阵元素。代码中还包含了一个示例矩阵，并打印出了spiralOrder函数的结果。

Java 版本

import java.util.ArrayList;
import java.util.List;

public class SpiralMatrix {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix.length == 0) return result;

        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (left <= right && top <= bottom) {
            // Traverse from left to right
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;

            // Traverse downwards
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            if (top <= bottom) {
                // Traverse from right to left
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;
            }

            if (left <= right) {
                // Traverse upwards
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        SpiralMatrix sm = new SpiralMatrix();
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        List<Integer> result = sm.spiralOrder(matrix);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

这段 Java 代码定义了一个SpiralMatrix类，其中包含了一个spiralOrder方法，它接收一个二维整数数组matrix作为参数，并返回一个整数列表，包含按顺时针螺旋顺序遍历的矩阵元素。main方法中给出了一个示例矩阵，并打印出了spiralOrder方法的结果。

Rust 版本

fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
    if matrix.is_empty() || matrix[0].is_empty() {
        return Vec::new();
    }

    let mut result = Vec::new();
    let (mut top, mut bottom) = (0, matrix.len() - 1);
    let (mut left, mut right) = (0, matrix[0].len() - 1);

    while left <= right && top <= bottom {
        // Traverse from left to right
        for i in left..=right {
            result.push(matrix[top][i]);
        }
        top += 1;

        // Traverse downwards
        if top <= bottom {
            for i in top..=bottom {
                result.push(matrix[i][right]);
            }
            right -= 1;
        }

        // Traverse from right to left
        if left <= right && top <= bottom {
            for i in (left..=right).rev() {
                result.push(matrix[bottom][i]);
            }
            bottom -= 1;
        }

        // Traverse upwards
        if top <= bottom {
            for i in (top..=bottom).rev() {
                result.push(matrix[i][left]);
            }
            left += 1;
        }
    }

    result
}

fn main() {
    let matrix = vec![
        vec![1, 2, 3],
        vec![4, 5, 6],
        vec![7, 8, 9],
    ];

    let order = spiral_order(matrix);
    for num in order {
        print!("{} ", num);
    }
}

这段 Rust 代码定义了一个spiral_order函数，它接收一个二维 i32 向量matrix作为参数，并返回一个 i32 向量，包含按顺时针螺旋顺序遍历的矩阵元素。main函数中给出了一个示例矩阵，并打印出了spiral_order函数的结果。

总结

上述代码提供了一个螺旋遍历二维矩阵的算法实现。无论是在 C++、Python、Java 还是 Rust 中，核心逻辑是相同的，主要步骤如下：

1. 初始化四个指针，分别代表矩阵的上边界top、下边界bottom、左边界left和右边界right。

2. 使用一个循环，按照从左到右、从上到下、从右到左、从下到上的顺序遍历矩阵的边界，并逐步缩小边界范围。

3. 在每一步遍历中，将遍历到的元素添加到结果列表中。

4. 每完成一次边界的遍历后，根据遍历的方向更新对应的边界指针。

5. 当左边界超过右边界或上边界超过下边界时，结束遍历。

这个算法的时间复杂度是 O(N)，其中 N 是矩阵中元素的总数，因为每个元素都被访问一次。空间复杂度是 O(N)，用于存储结果的空间。

不同编程语言的实现细节可能略有不同，例如在边界条件的检查和索引的更新上，但整体算法框架是一致的。