首页 > 代码库 > [LeetCode]Rotate Image
[LeetCode]Rotate Image
题目:旋转一个NxN的矩阵90度
要求常数空间复杂度。
思路:
从最外围开始,将第一行转到最后一列,最后一列转到最后一行,最后一行转到第一列,这是一个周期。
然后分别考虑上面周期中每个数的坐标对应关系。
例如:An*n:
a00 a01 a02 a03
a10 a11 a12 a13
a20 a21 a22 a23
a30 a31 a32 a33
则:a00->a03->a33->a30->a00
a01->a13->a32->a20->a01
a02->a23->a31->a10->a02
第一列到第二列是ai,j->aj,n-i-1
第二列到第三列是ai,j->aj,n-i-1
第三列到第四列是ai,j->aj,n-i-1
第四列到第五列是ai,j->aj,n-i-1
于是可以得到坐标的转换规律。
/*************************************************************************************************** You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? ***************************************************************************************************/ #include<stdio.h> void rotate(int** matrix, int matrixRowSize, int matrixColSize) { int i,j,k,temp,head = 0,tail = matrixRowSize - 1; while(head <= tail){ for(i = head;i < tail;i++){//转换一圈的坐标 j = matrixRowSize - head - 1; k = matrixRowSize - i - 1; temp = matrix[head][i]; matrix[head][i] = matrix[k][head]; matrix[k][head] = matrix[j][k]; matrix[j][k] = matrix[i][j]; matrix[i][j] = temp; } head++; tail--; } } void main(){ int num = 5; //int a[][3] = {{1,2,3},{4,5,6},{7,8,9}};//注意int**和int (*)[]的区别,int (*)[]是指向数组的指针,数组首址不可变 int **a = (int **)malloc(num*sizeof(int *)); for(int i = 0;i < num;i++){ a[i] = (int *)malloc(num*sizeof(int)); for(int j = 0;j < num;j++){ a[i][j] = num*i + j + 1; printf("%d ",a[i][j]); } printf("\n"); } rotate(a,num,num); for(int i = 0;i < num;i++){ for(int j = 0;j < num;j++) printf("%d ",a[i][j]); printf("\n"); } }
[LeetCode]Rotate Image
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。