算法练习-螺旋矩阵(思路+流程图+代码)

发布时间:2024年01月24日

难度参考

????????难度:中等

? ? ? ? 分类:数组

? ? ? ? 难度与分类由我所参与的培训课程提供,但需要注意的是,难度与分类仅供参考。以下内容均为个人笔记,旨在督促自己认真学习。

题目

????????给定一个正整数n,生成一个包含1到 n^2 所有元素,且元素按【顺时针】顺序螺旋排列的正方形矩阵。
示例1:
????????输入:n=3
????????输出:[[1,2,3],[8,9,4],[7,6,5]]

思路

????????题目要求生成一个顺时针螺旋排列的正方形矩阵,矩阵元素从1到n^2逐个递增。

  1. 初始化矩阵: 创建一个大小为n×n的矩阵,初始化所有元素为0。

  2. 定义边界: 使用四个变量topbottomleftright表示当前螺旋的边界。

  3. 顺时针填充矩阵: 使用循环,按照从左到右、从上到下、从右到左、从下到上的顺序填充矩阵。

  4. 更新边界: 每填充完一个方向后,更新相应的边界,确保下一轮填充在新的边界内进行。

  5. 重复步骤3和4: 循环执行步骤3和4,直到矩阵填充完成。

示例

????????考虑n=3的情况,即生成一个3×3的螺旋矩阵。

? ? ? ? 1.初始化矩阵:matrix = [[0, 0, 0], [0, 0, 0], [0, 0, 0]],

matrix = [
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0]
]

????????初始边界:top=0, bottom=2, left=0, right=2。

????????2.从左到右:matrix[0][0]=1, matrix[0][1]=2, matrix[0][2]=3

matrix = [
  [1, 2, 3],
  [0, 0, 0],
  [0, 0, 0]
]

????????更新top=1,

????????此时,top=1, bottom=2, left=0, right=2。

? ? ? ? 3.从上到下:matrix[1][2]=6, matrix[2][2]=9

matrix = [
  [1, 2, 3],
  [0, 0, 4],
  [0, 0, 5]
]

????????更新right=1,

????????此时,top=1, bottom=2, left=0, right=1。

? ? ? ? 4.从右到左:matrix[2][1]=8, matrix[2][0]=7

matrix = [
  [1, 2, 3],
  [0, 0, 4],
  [7, 6, 5]
]

????????更新bottom=1,

????????此时,top=1, bottom=1, left=0, right=1。

? ? ? ? 5.从下到上:matrix[1][0]=4

matrix = [
  [1, 2, 3],
  [8, 9, 4],
  [7, 6, 5]
]

????????更新left=1,

????????此时,top=1, bottom=1, left=1, right=1。

????????在每个方向上填充完后,我们更新相应的边界,并按照新的边界进行下一个方向的填充。这样,直到矩阵被填充完成。

梳理

? ? ? ? 本题主要逻辑是生成一个顺时针螺旋矩阵,其本质是通过模拟顺时针填充矩阵的过程。

  1. 初始化矩阵和边界指针:

    • 创建一个大小为 n x n 的矩阵,所有元素初始化为0。
    • 初始化四个指针 topbottomleftright 分别表示矩阵的上、下、左、右边界。
    • 初始化 num 用于填充矩阵的数字。
  2. 循环填充矩阵:

    • 在满足循环条件的情况下,按照顺时针的顺序从左到右、从上到下、从右到左、从下到上依次填充矩阵。
    • 在每个方向上,通过循环将 num 递增并填充到相应的位置。
  3. 逐步调整边界指针:

    • 每填充完一个方向后,逐步调整边界指针,确保下一次填充的方向不会重叠。
  4. 返回生成的矩阵:

    • 循环结束后,生成的矩阵即为顺时针螺旋矩阵。

????????本质上,这段代码通过模拟顺时针填充矩阵的过程,利用循环和边界指针的调整,逐步生成顺时针螺旋矩阵。这是一种常见的矩阵操作,通过巧妙的控制循环和边界指针,实现了一个相对简洁而高效的算法。

代码

#include <iostream>
#include <vector>

using namespace std;

// 生成顺时针螺旋矩阵
vector<vector<int>> generateMatrix(int n) {
    // 初始化矩阵
    vector<vector<int>> matrix(n, vector<int>(n, 0));

    // 设置边界指针
    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    int num = 1; // 用于填充矩阵的数字

    // 循环填充矩阵
    while (top <= bottom && left <= right) {
        // 从左到右
        for (int i = left; i <= right; ++i) {
            matrix[top][i] = num++;
        }
        top++;

        // 从上到下
        for (int i = top; i <= bottom; ++i) {
            matrix[i][right] = num++;
        }
        right--;

        // 从右到左
        if (top <= bottom) {
            for (int i = right; i >= left; --i) {
                matrix[bottom][i] = num++;
            }
            bottom--;
        }

        // 从下到上
        if (left <= right) {
            for (int i = bottom; i >= top; --i) {
                matrix[i][left] = num++;
            }
            left++;
        }
    }

    return matrix;
}

// 辅助函数:打印矩阵
void printMatrix(const vector<vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
}

int main() {
    int n = 3;
    
    // 生成螺旋矩阵
    vector<vector<int>> result = generateMatrix(n);

    cout << "生成的螺旋矩阵:" << endl;
    
    // 打印矩阵
    printMatrix(result);

    return 0;
}

????????时间复杂度:O(n^2)模拟过程相当于遍历了一遍二维矩阵。
????????空间复杂度:O(1)

打卡

文章来源:https://blog.csdn.net/qq_54813250/article/details/135829926
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。