【面试经典150 | 矩阵】螺旋矩阵

文章目录

  • 写在前面
  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
    • 方法一:模拟
    • 方法二:按层模拟
  • 写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【矩阵】【数组】


题目来源

54. 螺旋矩阵


题目解读

从矩阵左上角 (0, 0) 位置开始,按照顺时针旋转方向螺旋遍历依次输出矩阵的所有元素。


解题思路

方法一:模拟

本题一个直观的思路就是按照要求进行模拟。按照 “向右-向下-向左-向上” 的顺序遍历矩阵,读取每个位置的元素到答案数组中。

几个方向上的移动,可以通过坐标加减来实现,设当前位置坐标(行号和列号)为 (x, y),接下来是四个方向移动的坐标变换:

  • 向右:x 不变,y += 1
  • 向下:x += 1y 不变;
  • 向左:x 不变,y -= 1
  • 向上:x -= 1y 不变;

于是,定义一个表示方向的二维数组 dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}},注意第一维表示的方向要与 “向右-向下-向左-向上” 顺序一一对应。

我们还要使用一个数组 visited 来记录当前位置是否遍历过,如果遍历过,我们也要改变遍历的方向,因为要求是螺旋遍历输出所有的元素。

当前的移动方向索引用 dirIdx 表示,初始 dirIdx = 0 表示向右移动。我们从 (0, 0) 位置出发:

  • 将读取到的位置 (row, col) 对应的元素存入答案数组;
  • 更新数组 visited[row][col] = 1
  • 更新下一个将要遍历的位置即 nrow = row + dirs[dirIdx][0]ncol = col + dirs[dirIdx][1]
  • 如果下一个遍历的位置超出了矩阵的边界或者是已经遍历过的位置,那就要改变移动位置方向,即改变 dirIdx
  • 更新下一个位置的真正方向;
  • 如此遍历完所有位置,即可得到最后的答案数组。

实现代码

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();vector<int> ret(m*n);const int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int dirIdx = 0;int visited[m][n];memset(visited, 0, sizeof(visited));int i;int row = 0, col = 0;for(i = 0; i < m*n; ++i) {ret[i] = matrix[row][col];visited[row][col] = 1;int nrow = row + dirs[dirIdx][0];int ncol = col + dirs[dirIdx][1];if(nrow < 0 || nrow >= m || ncol < 0 || ncol >= n || visited[nrow][ncol]) {dirIdx = (dirIdx + 1) % 4;               }row += dirs[dirIdx][0];col += dirs[dirIdx][1];}return ret;}
};

复杂度分析

时间复杂度: O ( m n ) O(mn) O(mn) m m m 为矩阵 matrix 的行数, n n n 为列数。

空间复杂度: O ( 1 ) O(1) O(1)

方法二:按层模拟

可以将矩阵看成若干层,我们一层一层的输出元素。我们定义第 k 层为距离最近边界距离为 k 的所有顶点。

对于每层,我们从左上角开始以顺时针的顺序遍历所有元素。假设当前层的左上角为 (top, left),右下角为 (buttom, right),按照如下顺序进行遍历:

  • 从左到右遍历当前层的上部元素,(top, left)(top, right)
  • 从上到下遍历当前层的右部元素,(top+1, right)(buttom, right)
  • 如果 left < righttop < buttom,则从右到左遍历下部元素,(buttom, right-1)(buttom, left+1);从下到上遍历左部元素,(buttom, left)(top+1, left)

遍历完当前层的所有元素之后,更新层数为下一层,将 ++left++top--right--bottom。继续遍历,直到遍历完所有元素为止。

实现代码

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {if (matrix.size() == 0 || matrix[0].size() == 0) return {};int rows = matrix.size(), columns = matrix[0].size();vector<int> res;int left = 0, right = columns - 1, top = 0, bottom = rows - 1;	// 初始化为第一层while (left <= right && top <= bottom) {for (int column = left; column <= right; ++column) {		// 更新上部res.push_back(matrix[top][column]);}for (int row = top + 1; row <= bottom; ++row) {				// 更新右部res.push_back(matrix[row][right]);}if (left < right && top < bottom) {for (int column = right - 1; column > left; --column) {	// 更新下部res.push_back(matrix[bottom][column]);}for (int row = bottom; row > top; --row) {				// 更新左部res.push_back(matrix[row][left]);}}// 更新到下一层left++;right--;top++;bottom--;}return res;}
};

复杂度分析

时间复杂度: O ( m n ) O(mn) O(mn) m m m 为矩阵 matrix 的行数, n n n 为列数。

空间复杂度: O ( 1 ) O(1) O(1)


写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/145672.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

flink选择slot

flink选择slot 在这个类里修改 package org.apache.flink.runtime.resourcemanager.slotmanager.SlotManagerImpl; findMatchingSlot(resourceProfile)&#xff1a;找到满足要求的slot&#xff08;负责从哪个taskmanager中获取slot&#xff09;对应上图第8&#xff0c;9&…

[vue-admin-template实战笔记]

1.克隆项目 git clone gitgitee.com:panjiachen/vue-admin-template.git 2.安装依赖 npm install 3.运行项目就会自动打开网页&#xff0c;并且热部署插件 npm run dev 4.查看代码 //将vue-admin-template拖入到idea中即可查看代码 1)并且发现&#xff0c;常用的东西已经集…

从零手搓一个【消息队列】创建核心类, 数据库设计与实现

文章目录 一、创建核心类1, 交换机2, 交换机类型3, 队列4, 绑定5, 交换机转发 & 绑定规则6, 消息7, 消息属性 二、数据库设计1, 使用 SQLite2, 使用 MyBatis2.1, 创建 Interface2.2, 创建 xml 文件 三、硬盘管理 -- 数据库1, 创建 DataBaseManager 类2, init() 初始化数据库…

什么是AI客流量算法?如何应用在实际场景中?

客流量分析算法简而言之就是一种利用数据分析和机器学习技术进行人流量统计、预测和分析的算法。它能够根据不同的数据来源&#xff0c;如摄像头、传感器等&#xff0c;对特定区域内的客流量进行实时监测和分析&#xff0c;并通过对历史数据的综合分析&#xff0c;提供客流趋势…

ARM-day2

1、1到100累加 .text .global _start_start:MOV r0, #1ADD r1,r0, #1fun:ADD r0,r0,r1ADD r1,r1, #1cmp r1, #0x65moveq PC,LRbl funstop:b stop.end2、思维导图

Java基础---第十篇

系列文章目录 文章目录 系列文章目录一、说说Java 中 IO 流二、 Java IO与 NIO的区别(补充)三、java反射的作用于原理一、说说Java 中 IO 流 Java 中 IO 流分为几种? 按照流的流向分,可以分为输入流和输出流; 按照操作单元划分,可以划分为字节流和字符流; 按照流的角色…

java导出word(含图片、表格)

1.pom 引入 <!--word报告生成依赖--><dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>4.1.2</version></dependency><dependency><groupId>org.apache.poi</groupI…

【单片机】12-串口通信和RS485

1.通信有关的常见概念 区分&#xff1a;串口&#xff0c;COM口&#xff0c;UART&#xff0c;USART_usart和串口区别-CSDN博客 串口、COM口、UART口, TTL、RS-232、RS-485区别详解-CSDN博客 1.什么是通信 &#xff08;1&#xff09;人和人之间的通信&#xff1a;说话&#xff…

腾讯云 Cloud Studio 实战训练营结营活动获奖公示

点击链接了解详情 “腾讯云 Cloud Studio 实战训练营” 是由腾讯云联合 CSDN 推出的系列开发者技术实践活动&#xff0c;通过技术分享直播、动手实验项目、优秀代码评选、有奖征文活动等&#xff0c;让广大开发者沉浸式体验腾讯云开发者工具 Cloud Studio 的同时&#xff0c;实…

《数据结构、算法与应用C++语言描述》-栈的应用-开关盒布线问题

开关盒布线问题 问题描述 在开关盒布线问题中&#xff0c;给定一个矩形布线区域&#xff0c;其外围有若干管脚。两个管脚之间通过布设一条金属线路来连接。这条金属线路称为电线&#xff0c;它被限制在矩形区域内。两条电线交叉会发生电流短路。因此&#xff0c;电线不许交叉…

Python异步框架大战:FastAPI、Sanic、Tornado VS Go 的 Gin

一、前言 异步编程在构建高性能 Web 应用中起着关键作用&#xff0c;而 FastAPI、Sanic、Tornado 都声称具有卓越的性能。本文将通过性能压测对这些框架与Go的Gin框架进行全面对比&#xff0c;揭示它们之间的差异。 原文&#xff1a;Python异步框架大战&#xff1a;FastAPI、Sa…

【智能家居项目】裸机版本——项目介绍 | 输入子系统(按键) | 单元测试

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《智能家居项目》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 目录 &#x1f3c0;项目简介&#x1f3c0;输入子系统(按键)⚽应用层⚽设备层⚽ 内核层抽象层⚽…

每日一练-Q1-大数加法-20231001

目录 1.题目描述 2.输入描述 3.示例提示 4.问题分析 5.通过代码 1.题目描述 大数一直是一个c语言的一个难题。 现在我们需要你手动模拟出大数加法过程。 请你给出两个大整数加法结果。 2.输入描述 第一行输入整数n&#xff0c;第二行输入整数m。 (1<number<1e100)…

在nodejs中如何防止ssrf攻击

在nodejs中如何防止ssrf攻击 什么是ssrf攻击 ssrf&#xff08;server-side request forgery&#xff09;是服务器端请求伪造&#xff0c;指攻击者能够从易受攻击的Web应用程序发送精心设计的请求的对其他网站进行攻击。(利用一个可发起网络请求的服务当作跳板来攻击其他服务)…

10月1日作业

汇编指令合集 用select实现服务器并发代码 #include<myhead.h> #define IP "192.168.0.106" #define PORT 8888int main(int argc, const char *argv[]) {//新建套接字文件int sfd socket(AF_INET, SOCK_STREAM, 0);if(sfd < 0){ERR_MSG("socket&quo…

多线程学习笔记(一)

文章目录 1 线程基础知识复习2 CompletableFuture1、Future和Callable接口2、FutureTask3、对Future的改进4、案例精讲——电商5、常用方法6、CompetableFutureWithThreadPool【重要】 3 锁1、乐观锁和悲观锁2、synchronized 8锁案例3、公平锁和非公平锁4、可重入锁5、死锁及排…

web:[RoarCTF 2019]Easy Calc

题目 进入页面是一个计算器的页面 随便试了一下 查看源代码看看有什么有用的信息 访问一下这个calc.php 进行代码审计 <?php error_reporting(0); if(!isset($_GET[num])){show_source(__FILE__); }else{$str $_GET[num];$blacklist [ , \t, \r, \n,\, ", , \[, \]…

Win11下无法打开丛林之狐,提示未检测到DirectX 8.1

新装的win11系统&#xff0c;打开丛林之狐提示未检测到DirectX 8.1. 运行dxdiag检查DirectX版本&#xff1a; DX版本已经是12了&#xff1a; 最终参考了这篇文章解决了&#xff1a; 罪恶都市出现XX-directx version 8.1处理方法 - 知乎 控制面板 > 程序 > 启用或关闭Wi…

蜂蜜配送销售商城小程序的作用是什么

蜂蜜是农产品中重要的一个类目&#xff0c;其受众之广市场需求量大&#xff0c;但由于非人人必需品&#xff0c;因此传统线下门店经营也面临着痛点&#xff0c;线上入驻平台也有很多限制难以打造自有品牌&#xff0c;无法管理销售商品及会员、营销等&#xff0c;缺少自营渠道&a…

力扣 -- 718. 最长重复子数组

解题步骤&#xff1a; 参考代码&#xff1a; class Solution { public:int findLength(vector<int>& nums1, vector<int>& nums2) {int m nums1.size();int n nums2.size();//多开一行&#xff0c;多开一列vector<vector<int>> dp(m 1, ve…