Leetcode旋转数组

1.题目描述

给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。

不占用额外内存空间能否做到?

示例 1:

给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵,使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]


2.解答

昨天晚上遇到了一个类似的题目,也是二维数组尽心旋转,但是并没有给出是正方形矩阵,当时我想当然的以为就是正方形,没有考虑长方形矩阵的情况,如果二位矩阵为正方形,那么只需要在原始数组上进行覆盖即可,不需要额外的空间,而长方形数组就需要额外的空间了

class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null)  return;
        int n = matrix.length;
        for(int i = 0;i < n / 2;i++){
            for(int j = i;j < n - 1 - i;j++){
                int temp = 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] = temp;
            }
        }
    }
}

这个解法主要讲数组下标整清除就好了,使用i来控制旋转的层数,使用j来控制每一层需要进行旋转的个数,使用temp保存其实数值然后依次进行覆盖

这也是我印象中第一次自己完成的双百了

image


还有一种方法是参考题解里面的,这种解法需要一定经验,目前我没想到,不过下次就好了

image

主要就是对数组下标敏感一点,例如matrix[i][j] = matrix[n-1-i][j]就是关于中线对称,如果matrix[i][j] = matrix[j][i]就是关于主对角线对称

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;j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-i][j];
                matrix[n-1-i][j] = temp;
            }
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < i;j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

需要注意的是自己之前掌握的理论知识,一到自己写代码的时候居然忘了,这里只能使用temp变量在原方法中进行值得交换,不能使用swap函数进行交换,因为在swap方法的栈帧中是rotate方法中的副本,即使进行了交换,也不会影响到rotate方法中的变量

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode旋转数组