LeetCode 算法:螺旋矩阵c++

2024-06-12 01:04

本文主要是介绍LeetCode 算法:螺旋矩阵c++,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题链接🔗:螺旋矩阵
难度:中等⭐️⭐️

题目

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

示例 1
在这里插入图片描述

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2
在这里插入图片描述

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

提示
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 1

题解

四指针遍历法

  1. 题解

这个算法不需要修改原始矩阵。以下是实现这个算法的步骤:

  1. 初始化四个边界:top 表示矩阵的顶部边界,bottom 表示底部边界,left 表示左侧边界,right 表示右侧边界。
  2. 创建一个空列表 result 用于存储按螺旋顺序排列的元素。
  3. 使用一个循环,直到 top 大于 bottomleft 大于 right
    • leftright 遍历 top 行,将这些元素添加到 result
    • 增加 top 的值,缩小顶部边界。
    • topbottom 遍历 right 列,将这些元素添加到 result
    • 减少 right 的值,缩小右侧边界。
    • 如果 top 小于等于 bottom,从 rightleft 遍历 bottom 行,将这些元素添加到 result
    • 减少 bottom 的值,缩小底部边界。
    • 如果 left 小于等于 right,从 bottomtop 遍历 left 列,将这些元素添加到 result
    • 增加 left 的值,缩小左侧边界。
  4. 返回 result 列表,它包含了矩阵中所有元素的顺时针螺旋顺序。
  1. 复杂度:时间复杂度O(m×n),因为每个单元格都被填充一次;空间复杂度O(m×n),用于存储最终的矩阵。
  2. 过程

螺旋矩阵是一种特殊的矩阵,其元素按照螺旋的方式填充,从外圈向内圈逐渐填充,每个元素的值依次递增。

实现过程如下:

  1. 首先,函数检查输入矩阵是否为空或其子数组是否为空。如果是,则直接返回一个空的一维数组。

  2. 定义四个变量top, bottom, left, right来分别表示矩阵的上边界、下边界、左边界和右边界。

  3. 使用一个while循环,当top不大于bottomleft不大于right时,循环继续。这确保了矩阵中至少还有一行或一列可以遍历。

  4. 在循环内部,首先从leftright遍历矩阵的顶部行,将这些元素添加到结果数组中,然后top加1。

  5. 接着,从topbottom遍历矩阵的最右列,将这些元素添加到结果数组中,然后right减1。

  6. 确保在继续之前,当前的遍历行与上一次的遍历行不同(如果top小于等于bottom),从rightleft遍历矩阵的底部行,然后bottom减1。

  7. 同样,确保在继续之前,当前的遍历列与上一次的遍历列不同(如果left小于等于right),从bottomtop遍历矩阵的最左列,然后left加1。

  8. 函数最后返回包含矩阵所有元素的一维数组,这些元素按照螺旋顺序排列。

main函数中创建了3x3、3x4的两个矩阵,并调用spiralOrder函数来获取螺旋顺序的元素,然后打印这些元素。

  1. c++ demo
#include <iostream>
#include <vector>std::vector<int> spiralOrder(const std::vector<std::vector<int>>& matrix) {if (matrix.empty() || matrix[0].empty()) return {};std::vector<int> result;int top = 0, bottom = matrix.size() - 1;int left = 0, right = matrix[0].size() - 1;while (top <= bottom && left <= right) {// 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;// Make sure we are now on a different row.if (top <= bottom) {for (int i = right; i >= left; --i) {result.push_back(matrix[bottom][i]);}--bottom;}// Make sure we are now on a different column.if (left <= right) {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> spiral = spiralOrder(matrix);for (int num : spiral) {std::cout << num << " ";}std::cout << std::endl;std::vector<std::vector<int>> matrix2 = {{1, 2,  3,  4 },{5, 6,  7,  8 },{9, 10, 11, 12}};std::vector<int> spiral2 = spiralOrder(matrix2);for (int num : spiral2) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
  • 输出结果:

1 2 3 6 9 8 7 4 5
1 2 3 4 8 12 11 10 9 5 6 7
在这里插入图片描述

这篇关于LeetCode 算法:螺旋矩阵c++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1052762

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程