上海网站邮箱制作,小游戏制作软件,做一的同志小说网站,门户网站英文版建设文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;原地旋转方法二#xff1a;翻转代替旋转 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带… 文章目录 写在前面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 ((n1)/2) (n2−1)/4((n−1)/2)×((n1)/2) 个位置。
实现代码
class Solution {
public:void rotate(vectorvectorint 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(vectorvectorint 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)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
