【面试经典150 | 矩阵】旋转图像

文章目录

  • 写在前面
  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
    • 方法一:原地旋转
    • 方法二:翻转代替旋转
  • 写在最后

写在前面

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

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

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

Tag

【原地操作】【数组】


题目来源

面试经典150 | 48. 旋转图像


题目解读

有一个二维矩阵,需要将二维矩阵顺时针旋转 90°,也就是行变到别的列(或者列变到别的行)操作。


解题思路

方法一:原地旋转

四位置元素交换

我们知道本题中的旋转操作就是将行和列进行相应的转换,具体的就是将 (i, j) 位置元素转移到 (j, n - 1 - i)位置,其中 n 为矩阵的行数(或者列数)。比如旋转操作会将第一行第二列位置的元素转移到第二行最后一列的位置。

题目中要求我们进行原地旋转,原地旋转就是在原矩阵中利用当前位置的元素去覆盖旋转后的位置,用原旋转后的位置元素去覆盖该旋转位置旋转后的位置…,如果进行四次旋转直到回到初始的位置。比如说现在的位置是 (i, j),记为位置 1

  • (i, j) 旋转后的位置为 (j, n - 1 - i),记为位置 2
  • (j, n - 1 - i) 旋转后的位置为 (n - 1- i, n - 1 - j),记为位置 3
  • (n - 1- i, n - 1 - j) 旋转后的位置为 (n - 1 - j, i),记为位置 4

原地旋转操作就是实现以上四个位置元素的交换。交换示意图如下所示。

枚举的位置范围

n 为偶数的时候,我们需要枚举 n 2 / 4 = ( n / 2 ) × ( n / 2 ) n^2 / 4 = (n/2) \times (n/2) n2/4=(n/2)×(n/2) 个位置;
n 为奇数时,由于中心的位置经过旋转后位置不变,我们需要枚举 ( n 2 − 1 ) / 4 = ( ( n − 1 ) / 2 ) × ( ( n + 1 ) / 2 ) (n^2-1) / 4 = ((n-1)/2) \times ((n+1)/2) (n21)/4=((n1)/2)×((n+1)/2) 个位置。

实现代码

class Solution {
public:void rotate(vector<vector<int>>& matrix) {// 原地操作int n = matrix.size();for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < (n + 1) / 2; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[n-j-1][i];matrix[n-j-1][i] = matrix[n-i-1][n-j-1];matrix[n-i-1][n-j-1] = matrix[j][n-i-1];matrix[j][n-i-1] = temp;}}}
};

复杂度分析

时间复杂度: O ( n 2 ) O(n^2) O(n2) n n n 为矩阵 matrix 的行数(列数)。

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

方法二:翻转代替旋转

还有一种实现原地旋转的方法,那就是利用翻转来代替旋转。具体地:

首先对矩阵进行水平翻转(第一行变成最后一行,第二行变成倒数第二行,…),然后再对矩阵沿着主对角线方向进行翻转,这样就实现了矩阵顺时针旋转 90° 的操作了。

以上的翻转就是交换操作。

实现代码

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();// 水平翻转for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < n; ++j) {swap(matrix[i][j], matrix[n-1-i][j]);}}// 主对角线翻转for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {swap(matrix[i][j], matrix[j][i]);}}}
};

复杂度分析

时间复杂度: O ( n 2 ) O(n^2) O(n2) n n n 为矩阵 matrix 的行数(列数)。

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


写在最后

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

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

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

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

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

相关文章

Flask实现注册登录模块

&#x1f64c;秋名山码民的主页 &#x1f602;oi退役选手&#xff0c;Java、大数据、单片机、IoT均有所涉猎&#xff0c;热爱技术&#xff0c;技术无罪 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; 获取源码&#xff0c;添加WX 目录 前言1.…

几道web题目

总结几道国庆写的web题目 [ACTF2020 新生赛]Include1 点进去发现就一个flag.php,源代码和抓包都没拿到好东西 结合题目猜是文件包含&#xff0c;构建payload ?filephp://filter/readconvert.base64-encode/resourceflag.php 得到base64编码过的flag&#xff0c;解码即可 此题…

Android---Class 对象在执行引擎中的初始化过程

一个 class 文件被加载到内存中的步骤如下图所示&#xff1a; 装载 装载是指 Java 虚拟机查找 .class 文件并生成字节流&#xff0c;然后根据字节流创建 java.lang.Class 对象的过程。 1. ClassLoader 通过一个类的全限定名&#xff08;包名类名&#xff09;来查找 .class 文件…

Linux多线程

文章目录 多线程多线程概念多线程优点多线程缺点线程和进程 Linux线程控制POSIX线程库线程的创建进程ID获取线程终止线程等待线程分离 总结 多线程 多线程概念 在Linux中&#xff0c;线程是进程内的执行单元。换句话说&#xff0c;线程是进程内部的子任务&#xff0c;它们共享…

入侵防御系统(IPS)网络安全设备介绍

入侵防御系统&#xff08;IPS&#xff09;网络安全设备介绍 1. IPS设备基础 IPS定义 IPS&#xff08;Intrusion Prevention System&#xff09;是一种网络安全设备或系统&#xff0c;用于监视、检测和阻止网络上的入侵尝试和恶意活动。它是网络安全架构中的重要组成部分&…

MyBatis中的ResultMap有什么作用

MyBatis是一款广泛使用的Java持久层框架&#xff0c;它简化了数据库访问和数据映射的工作。在MyBatis中&#xff0c;ResultMap是一个强大的工具&#xff0c;用于将数据库查询结果映射到Java对象上。本文将深入探讨MyBatis中的ResultMap&#xff0c;解释它的作用以及如何使用它来…

进程状态的理解

我们知道进程会有属于自己的PCB&#xff0c;便于操作系统的管理&#xff0c;而PCB结构体里面还有进程状态参数&#xff0c;类似于用一个变量标识对应的进程状态&#xff0c;就相当于将每个进程状态编号&#xff0c;而PCB中有一个变量存储当前进程状态所对应的编号&#xff0c;也…

解决WordPress升级后提示:无需升级,您的WordPress数据库已经是最新的了

问题描述 当升级了 WordPress 6.3 后&#xff0c;登录后台出现了提示&#xff1a;无需升级&#xff0c;您的WordPress 数据库已经是最新的了。并且无法进入后台了。 出现这个问题的原因可能是你网站开启了 Memcached 缓存。 如何验证是否开启了 Memcached 缓存&#xff1f;检…

php 安装mongodb扩展模块,rdkafka模块

mongodb mongodb扩展下载 选择php版本&#xff0c;根据报错提示&#xff0c;选择扩展对应的版本选择非安全进程将php_mongodb.dll放到php/ext目录下修改php.ini配置&#xff0c;添加extensionphp_mongodb.dll开启php_mongodb扩展&#xff0c;重启服务php -m 查看是否开启成功…

排序(order by)

MySQL从小白到总裁完整教程目录:https://blog.csdn.net/weixin_67859959/article/details/129334507?spm1001.2014.3001.5502 语法格式: select */列名 from 表名 order by 列名1 asc/desc, 列名2 asc/desc; 说明&#xff1a; 排序的目的&#xff1a;改变查询结果的返回顺序…

大数据软件项目的数据清洗

大数据软件项目中的数据清洗是数据预处理过程中的重要环节&#xff0c;用于识别和纠正数据集中的错误、不一致性和不完整性。虽然没有专门的"数据清洗开发框架"&#xff0c;但有许多工具和库可用于数据清洗任务。以下是一些常见的数据清洗工具和库&#xff0c;可以与…

win10 U盘安装教程

一年内&#xff0c;第三次重装电脑了&#xff0c;我必须要写一份教程了。从制作U盘开始&#xff0c;到重装系统&#xff0c;全部都记录一下&#xff0c;以备不时之需。 首先&#xff0c;找一个U盘&#xff0c;如果U盘内有需要文件&#xff0c;请自行备份&#xff0c;因为这个U盘…

JVM(Java虚拟机)

目录 1.JVM 简介 1.1 JVM 发展史 1.Sun Classic VM 2.Exact VM 3.HotSpot VM 4.JRockit 5.J9 JVM 6.Taobao JVM&#xff08;国产研发&#xff09; 1.2 JVM 和《Java虚拟机规范》 2. JVM 运行流程 JVM 执行流程 3. JVM 运行时数据区 3.1 堆&#xff08;线程共享&…

泛型的小结

文章目录 什么是泛型泛型的相关概念泛型的作用 泛型的使用泛型类语法泛型接口语法泛型方法语法泛型类的简单示例泛型接口的简单示例基于泛型的简单工厂方法泛型的上界与下界 泛型的一些使用建议 什么是泛型 从JDK1.5开始引入泛型&#xff08;generic&#xff09;语法。对类型实…

一文看懂光模块的工作原理

你们好&#xff0c;我的网工朋友 光模块有很多类别&#xff0c;是我们经常要用到的PHY层器件。虽然封装&#xff0c;速率&#xff0c;传输距离有所不同&#xff0c;但是其内部组成基本是一致的。 以太网交换机常用的光模块有SFP&#xff0c;GBIC&#xff0c;XFP&#xff0c;X…

【Linux】 rm命令使用

作为一个程序员 我们经常用到rm -rf * 或者rm -rf XXX 。但是rm -rf 是什么意思不是很清楚&#xff0c;咱们一起来学习一下吧。 rm&#xff08;英文全拼&#xff1a;remove&#xff09;命令用于删除一个文件或者目录。 rm 命令 -Linux手册页 著者 由保罗鲁宾、大卫麦肯齐、理…

10.8队列安排,最少找字典次数,表达式转换与计算模拟(栈、队列)

队列安排1160 灵活的插入与删除 用队列实现的话&#xff0c;就是双端队列&#xff0c; 第一阶段是要找到对应编号的同学&#xff0c;然后根据p的取值决定是怎么插入 第二阶段也是要找到对应编号同学&#xff0c;之后就删除&#xff0c;如果找不到就返回 思路是这个思路&…

为什么团队需要实时协作?该如何实现?

协作是任何组织成功的关键部分&#xff0c;通过明确定义的愿景和使命并基于透明度和持续沟通来执行。 实时的协作是指员工之间就不同的项目、任务、文件或文档进行同步、无缝的互动和协作&#xff0c;他们几乎不受任何地理边界的限制&#xff0c;即时沟通和分享反馈、想法和信…

【AI视野·今日Robot 机器人论文速览 第四十七期】Wed, 4 Oct 2023

AI视野今日CS.Robotics 机器人学论文速览 Wed, 4 Oct 2023 Totally 40 papers &#x1f449;上期速览✈更多精彩请移步主页 Interesting: &#x1f4da;基于神经网络的多模态触觉感知, classification, position, posture, and force of the grasped object多模态形象的解耦(f…

从零开始的C++(七)

1.malloc、free和new、delete的区别&#xff1a; 1、.malloc、free是函数&#xff0c;new、delete是运算符。 2、malloc不会调用构造函数&#xff0c;new可以调用构造函数。 3、malloc开辟失败返回NULL&#xff0c;new失败会捕捉异常。 4、malloc不会自动计算类型大小&…