问题描述
https://leetcode.com/problems/rotate-image/
解决思路
遇到这种旋转题目，可以考虑用对折的方法。举例而言：
[1,2,3]
[4,5,6]
[7,8,9]
沿着1,5,9这一斜对角对折，变成了：
[1,4,7]
[2,5,8]
[3,6,9]
再沿着中间列4,5,6对折，变成了：
[7,4,1]
[8,5,2]
[9,6,3]
即为结果。
要特别注意的是，第一次对折的第二个for循环，j = i + 1,限制在右上角元素交换位置，否则j = 0开始会两次对折，回到原始状态。
代码
class Solution {
public void rotate(int[][] matrix) {
//folding the matrix according to lower corner
for(int i = 0; i < matrix.length; i++){
for(int j = i + 1; j < matrix[0].length; j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
//folding the matrix according to the middle column
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length/2 ; j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length - 1 - j];
matrix[i][matrix.length - 1 - j] = temp;
}
}
}
}
复杂度分析
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
