1. 首页
  2. Leetcode经典148题

leetCode-48-Rotate-Image

题目描述(中等难度)

leetCode-48-Rotate-Image

将一个矩阵顺时针旋转 90 度,并且不使用额外的空间。大概属于找规律的题,没有什么一般的思路,观察就可以了。

解法一

可以先转置,然后把每列对称交换交换一下。

leetCode-48-Rotate-Image

public void rotate(int[][] matrix) {
    //以对角线为轴交换
    for (int i = 0; i <  matrix.length; i++) {
        for (int j = 0; j <=i; j++) {
            if (i == j) {
                continue;
            }
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    } 
    //交换列
    for (int i = 0, j = matrix.length - 1; i < matrix.length / 2; i++, j--) {
        for (int k = 0; k < matrix.length; k++) {
            int temp = matrix[k][i];
            matrix[k][i] = matrix[k][j];
            matrix[k][j] = temp;
        }
    }

} 

时间复杂度:O(n²)。

空间复杂度:O(1)。

也可以先以横向的中轴线为轴,对称的行进行交换,然后再以对角线交换。

解法二

我把这个链接的思路贴过来,里边评论有张图也都顺道贴过来吧,写的很好。

leetCode-48-Rotate-Image

一圈一圈的循环交换,很妙!

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

时间复杂度:O(n²)。

空间复杂度:O(1)。

这道题就是对题目的特征进行观察就可以了。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-48-Rotate-Image

链接:https://www.javajike.com/article/3185.html

« leetCode-47-Permutations-II
leetCode-49-Group-Anagrams»

相关推荐

QR code