LeetCode热题100 48.旋转图像

题目描述

给定一个 × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1:

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

示例 2:

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

提示:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

解题思路

可以摸索下有什么规律可寻,以示例二为例,枚举矩阵元素旋转90º后位置变化

第一行

5:        (0,0) ——> (0,3)

1:          (0,1) ——> (1,3)

9:        (0,2) ——> (2,3)

11:          (0,3) ——> (3,3)

第二行

2:        (1,0) ——> (0,2)

4:          (1,1) ——> (1,2)

······

由此可以总结出一个矩阵元素旋转后的位置变化公式:matrix[i][j]  ——>  matrix[j][n-1-i]

🤔

如果直接修改矩阵元素,前一个元素会覆盖掉它旋转后位置的元素,会造成数据丢失,如果将两个元素交换的话又会打乱矩阵,这样的话好像得借助一个辅助矩阵来临时储存元素,但是题目要求原地修改矩阵,不能借助另一个矩阵,啊,到底要怎么做,一定还有什么规律没有发现,盯着矩阵好好想想吧······

n坤时后——  

山重水复疑无路,柳暗花明又一村。

我发现将每行元素反转后,每个元素以副对角线对称位置就是原位置旋转后的位置,

原矩阵 \begin{bmatrix} 5&1 &9 &11 \\ 2&4 &8 &10 \\ 13& 3 &6 &7 \\ 15&14 &12 &16 \end{bmatrix}        每行反转——>        \begin{bmatrix} 11 &9 &1 &5 \\ 10 &8 &4 &2 \\ 7 &6 &3 &13 \\ 16& 12 &14 &15 \end{bmatrix} 

\begin{bmatrix} 11 &9 &1 &5 \\ 10 &8 &4 &2 \\ 7 &6 &3 &13 \\ 16& 12 &14 &15 \end{bmatrix}        以副对角线翻转——>        \begin{bmatrix} 15 &13 &2 &5 \\ 14& 3& 4& 1\\ 12&6 &8 &9 \\ 16&7 & 10 &11 \end{bmatrix}

用公式表示:

matrix[i][j]   反转  ——>  matrix[i][n-1-j]

(以副对角线翻转元素位置变化公式为:  matrix[i][j]——>matrix[n-1-j][n-1-i] )

matrix[i][n-1-j]   以副对角线翻转 ——> matrix[n-1-(n-1-j)][n-1-i]=matrix[j][n-1-i]

由此可见,通过以上操作后就可以间接将矩阵中的每个元素移到旋转后的位置。

算法流程:

1.对矩阵每行反转

2.实现副对角线翻转操作,就是将矩阵副对角线两侧元素交换。

以下是算法Java实现:

class Solution {
    public void rotate(int[][] matrix) {
        int n=matrix.length;
        // 反转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n- j - 1] = temp;
            }
        }
        // 副对角线翻转
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-i-1;j++){
                int t=matrix[i][j];
                matrix[i][j]=matrix[n-j-1][n-i-1];
                matrix[n-j-1][n-i-1]=t;
            }
        }
    }
}

时间复杂度为O(n^2),空间复杂度为O(1)


其他方法

大自然的搬运工。

作者:

Krahets

以位于矩阵四个角点的元素为例,设矩阵左上角元素 A 、右上角元素 B 、右下角元素 C 、左下角元素 D 。矩阵旋转 90º 后,相当于依次先后执行 D→A,C→D ,B→C,A→B 修改元素,即如下「首尾相接」的元素旋转操作:

                                                A←D←C←B←A

如上图所示,由于第 1 步 D→A 已经将 A 覆盖(导致 A 丢失),此丢失导致最后第 4 步 A→B 无法赋值。为解决此问题,考虑借助一个「辅助变量 tmp」预先存储 A ,此时的旋转操作变为:

                                        暂存 tmp=A

                                        A←D←C←B←tmp

如上图所示,一轮可以完成矩阵 4 个元素的旋转。因而,只要分别以矩阵左上角 1/4的各元素为起始点执行以上旋转操作,即可完整实现矩阵旋转。

具体来看,当矩阵大小 n 为偶数时,取前 n/2行、前 n/2列的元素为起始点;当矩阵大小 n 为奇数时,取前 n/2行、前 (n+1)/2列的元素为起始点。

令 matrix[i][j]=A ,根据文章开头的元素旋转公式,可推导得适用于任意起始点的元素旋转操作:

暂存tmp=matrix[i][j]

matrix[i][j]←matrix[n−1−j][i]←matrix[n−1−i][n−1−j]←matrix[j][n−1−i]←tmp

算法执行流程:

算法Java实现:

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < (n + 1) / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
    }
}

复杂度分析
时间复杂度O(N^2) : 其中 N 为输入矩阵的行(列)数。需要将矩阵中每个元素旋转到新的位置,即对矩阵所有元素操作一次,使用O(N^2) 时间。
空间复杂度 O(1) : 临时变量 tmp使用常数大小的额外空间。值得注意,当循环中进入下轮迭代,上轮迭代初始化的 tmp占用的内存就会被自动释放,因此无累计使用空间。


力扣官方题解

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue 内置指令-v-pre/v-memo

一、v-pre 使用了该指令的元素和子元素会被编译忽略&#xff0c;也就是不进行编译&#xff0c;其中包含的所有vue模版语法都会原样显示&#xff0c;作用加快vue的编译 例子&#xff1a; <p v-pre>{{不会被编译}}<span v-text"msg"></span></p&…

部署K8S

防火强的初始化&#xff1a; [rootk8s-node-12 ~]# systemctl stop firewalld NetworkManager [rootk8s-node-12 ~]# systemctl disable firewalld NetworkManager Removed symlink /etc/systemd/system/multi-user.target.wants/NetworkManager.service. Removed symlink /et…

Flask 路由机制分析之一

一、前言 《Flask Run运行机制剖析》这篇我们讲了应用启动的内部机制&#xff0c;启动后就开始监听Http请求了&#xff0c;请求过来如何跳到对应的函数执行&#xff0c;这就是路由机制。我们沿用上一篇例子&#xff0c;来探究一下app.route("/")内部干了些什么事。 …

力扣 三数之和 双指针 java

Problem: 15. 三数之和 时间复杂度: O ( n 2 ) O(n^2) O(n2) &#x1f351; AC code class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res new ArrayList<>();int len nums.length; if(len < 3…

【ARM Trace32(劳特巴赫) 使用介绍 2 -- Trace32 cmm 脚本基本语法及常用命令】

文章目录 Trace32 CMM 概述1.1 Trace32 系统命令 SYStem1.1.1 Trace32 SYStem.CONFIG1.1.2 SYStem.MemAccess1.1.3 SYStem.Mode1.1.3.1 TRST-Resets the JTAG TAP controller and the CPU internal debug logic1.1.3.2 SRST- Resets the CPU core and peripherals 1.2 Trace32 …

PostgreSQL InvalidMessage Cache 同步机制

文章目录 背景InvalidMessages 基本类型InvalidMessages 数据结构概览共享内存 的 "ring-buffer" 结构Backend 本地的 InvalidMessages管理SharedInvalCatalogMsgSharedInvalCatcacheMsgSharedInvalRelcacheMsgSharedInvalSnapshotMsgSharedInvalSmgrMsgSharedInvalR…

【软考】14.3 设计模式

《设计模式》 有下划线&#xff1a;类模式 / 对象模式无下划线&#xff1a;对象模式 创建型 设计模式 创建对象 构建器&#xff08;Builder&#xff09;&#xff1a;类和构造分离抽象工厂&#xff08;Abstract Factory&#xff09;&#xff1a;抽象接口工厂&#xff08;Factor…

ChatGPT 驱动软件开发:AI 在软件研发全流程中的革新与实践

目录 内容简介作者简介专家推荐读者对象目录直播预告 计算机技术的发展和互联网的普及&#xff0c;使信息处理和传输变得更加高效&#xff0c;极大地改变了金融、商业、教育、娱乐等领域的运作方式。数据分析、人工智能和云计算等新兴技术&#xff0c;也在不断地影响和改变着各…

怎么搭建一个蛋糕店小程序?

在当今的移动互联网时代&#xff0c;很多企业纷纷选择了小程序作为推广和销售的利器。对于蛋糕店来说&#xff0c;创建一个小程序可以提高品牌知名度&#xff0c;增加销售渠道。下面&#xff0c;我们以【乔拓云】第三方平台为例&#xff0c;来介绍一个完整蛋糕店小程序的制作流…

TiDB x 汉口银行丨分布式数据库应用实践

汉口银行是一家城市商业银行&#xff0c;近年来专注科技金融、民生金融等领域。在数据库国产化改造中&#xff0c;汉口银行引入了 TiDB 数据库&#xff0c;并将其应用在重要业务系统&#xff1a;头寸系统中&#xff0c;实现了一栈式的数据服务&#xff0c;同时满足了高并发、低…

【0基础学Java第四课】-- 逻辑控制

4. 逻辑控制 4.1 顺序结构4.2 分支结构4.2.1 if语句判断一个数字是奇数还是偶数判断一个数字是正数&#xff0c;负数&#xff0c;还是零判断一个年份是否为闰年 4.2.2 switch 语句 4.3 while循环打印 1 - 10 的数字计算 1 - 100 的和计算 5 的阶乘计算1&#xff01;2&#xff0…

如何查看多开的逍遥模拟器的adb连接端口号

逍遥模拟器默认端口号为&#xff1a;21503。 不过&#xff0c;使用多开器多开的时候&#xff0c;端口就不一定是21503了。 如何查看&#xff1f; 进入G:\xiaoyao\Microvirt\MEmu\MemuHyperv VMs路径中 每多开一个模拟器&#xff0c;就会多出一个文件夹。 进入你要查找端口号…

MATLAB R2018b详细安装教程(附资源)

云盘链接&#xff1a; pan.baidu.com/s/1SsfNtlG96umfXdhaEOPT1g 提取码&#xff1a;1024 大小&#xff1a;11.77GB 安装环境&#xff1a;Win10/Win8/Win7 安装步骤&#xff1a; 1.鼠标右击【R2018b(64bit)】压缩包选择【解压到 R2018b(64bit)】 2.打开解压后的文件夹中的…

leetcode:1207. 独一无二的出现次数(python3解法)

难度&#xff1a;简单 给你一个整数数组 arr&#xff0c;请你帮忙统计数组中每个数的出现次数。 如果每个数的出现次数都是独一无二的&#xff0c;就返回 true&#xff1b;否则返回 false。 示例 1&#xff1a; 输入&#xff1a;arr [1,2,2,1,1,3] 输出&#xff1a;true 解释&…

RabbitMQ消息中间件

一、初始MQ 首先了解一下微服务间通讯有同步和异步两种方式&#xff1a;- 同步通讯&#xff1a;是指两个或多个系统在进行信息交换时&#xff0c;必须在同一时刻进行操作 - 异步通讯&#xff1a;是指两个或多个系统之间的通讯方式&#xff0c;其中发送方和接收方不是在同一时刻…

Hadoop学习总结(搭建Hadoop集群(伪分布式模式))

如果前面有搭建过Hadoop集群完全分布式模式&#xff0c;现在搭建Hadoop伪分布式模式可以选择直接克隆完全分布式模式中的主节点(hadoop001)。以下是在搭建过完全分布式模式下的Hadoop集群的情况进行 伪分布式模式下的Hadoop功能与完全分布式模式下的Hadoop功能相同。 一、克隆…

day55--动态规划13

300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组 第一题&#xff1a;最长递增子序列 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列&#xff0c;删除&#xff08;或不删除&#xff09;数组中的元素而…

软测推荐第二期:10本高质量测试书籍

在不断发展的软件开发领域&#xff0c;测试是质量的守护者&#xff0c;确保产品不仅满足功能要求&#xff0c;而且提供无缝的用户体验。随着软件复杂性的增加&#xff0c;对完善的测试方法和见解的需求也随之增加。 上次给大家推荐了五本书&#xff0c;获得了大家的积极反馈&a…

二叉搜索树的最小绝对差[简单]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你一个二叉搜索树的根节点root&#xff0c;返回树中任意两不同节点值之间的最小差值。差值是一个正数&#xff0c;其数值等于两值之差的绝对值。 示例 1&#xff1a; 输入&#xff1a;root [4,2,6,1,3] 输出&#xff1a;1 示例 …