题解 | #【冲刺双百】顺时针旋转矩阵#

顺时针旋转矩阵

http://www.nowcoder.com/practice/2e95333fbdd4451395066957e24909cc

时间复杂度为O(1)的思路

  1. 想要控制时间复杂度在O(1)则需要在原矩阵上操作
  2. 寻找规律:分析顺时针旋转后位置的变化,得到:

mat[i][j]->m[j][n-1-i]
构造出坐标转移方程:f(i,j)=(j,n-1-i)
设f_next0=(i,j) 继续推导:

  • f_next1=f(i,j)=(j,n-1-i)
  • f_next2=f(j,n-1-i)=(n-1-i,n-1-j)
  • f_next3=f(n-1-i,n-1-j)=(n-1-j,i)
  • f_next4=f(n-1-j,i)=(i,j)
    发现规律,周期为4,意味着每四个结点一组交换位置即达到旋转效果
  1. 为了避免重复旋转,接下来只需要确定每一组中哪一个节点做旋转即可
  • 其实画到四阶矩阵就可以发现:
    假设我们从左上角开始:
    • 第一行的前n-1个位置都需要旋转操作
    • 第二行从第2个位置开始的n-2-1个位置需要操作 ……
    • 如果当前行n-2=1,则该组只有一个结点(四个位置重合了)不需要旋转

    归纳出:
    对于n阶矩阵,前(n+1)/2行需要旋转,从第一行开始,往下每行需要旋转的位置都减少2
    每行开始位置横纵下表相等

    • 代码中inner为当前有效基数(每行-2)
import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        int idx=0;
        int inner=n;
        while(idx<=n/2-1&&inner>1){
            int col=idx;
            for(int i=1;i<inner;i++){
                swap(mat,idx,col,n);
                col++;
            }
            inner-=2;
            ++idx;
        }
        return mat;
    }
    
    public void swap(int[][] mat,int i, int j,int n){
        int temp=mat[i][j];
        mat[i][j]=mat[j][n-1-i];
        mat[j][n-1-i]=temp;
        temp=mat[i][j];
        mat[i][j]=mat[n-1-i][n-1-j];
        mat[n-1-i][n-1-j]=temp;
        temp=mat[i][j];
        mat[i][j]=mat[n-1-j][i];
        mat[n-1-j][i]=temp;
    }
}
全部评论

相关推荐

头像
03-14 11:23
已编辑
北京邮电大学 管理咨询
211勇闯初创小公司头破血流系列3这件事不是发生在我身上的,但前同事们参与创作的积极性空前高涨,为了习惯,还是都采用第一人称的视角来看这出大戏。有一天老板在我们的眼皮底下接了一个电话,最终敲定了去北京出差的时间,下周一。他得意洋洋地说,这单下来保底五百万的流水,如果成了,我们都能得到五位数的提成。这对于一群刚上班的人来说是天大的诱惑,我们经历了周末的无偿加班,把他去北京所需要的文件都准备好了。只是在去北京的周一当天,老板睡过头了。整个上午都没见他的踪影,给他发文件也不会,打电话问问题也不接,直到中午才姗姗来迟。当然,这只是拉开了这场恐怖出差的序幕。只见他来了也不紧不慢的,手指在办公室转了一圈,...
姜大力:补充: 1.五百万的单子根本没有五百万,只是过去展示拼装的产品并简单考察。该项目只是竞标,项目内容是商业街区改造; 2.决策是当天上午10点半左右老板珊珊来迟后突发奇想去北京,中午1点在催促下着急出发,没有任何出差补助; 3.出发之前已经知道进京证不好使了,但还是执意要开车去; 4.实习生实打实连续开了***小事车,非常辛苦,工资在转正后只有两千五; (有疑问会继续补充)
点赞 评论 收藏
分享
MScoding:你这个实习有一个是当辅导老师,这个和找技术岗没有关系吧?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务