LeetCode 48 - Rotate Image

作者 QIFAN 日期 2017-01-18
LeetCode 48 - Rotate Image

原题链接: 48. Rotate Image


题干

给定一个 n * n 的矩阵,要求将它顺时针旋转 90 度。

Follow up :
可以 in-place 吗?

思路

简单粗暴的思路是再新建一个矩阵,给定矩阵从上到下将元素复制到新矩阵从右往左。这个时间复杂度为 $O(N^2)$ ,空间复杂度为 $O(N^2)$ 。

如果要 in-place ,只需找出交换的规律。同样是以中心为轴,上边变成右边,右边变成下边,下边变成左边,左边变成上边。一个点到另一个点,只需要爬过长度为 n 的边长,和蚂蚁一样。

  • 若在上边,列号加到头,再加行号
  • 若在右边,行号加到头,再减列号
  • 若在下边,列号减到头,再减行号
  • 若在左边,行号减到头,再加列号

因为是空间 $O(1)$ ,那就是四条边同一位置的元素一起换,如果一条边一起换那就是空间 $O(N)$ 了。从最外围的边开始,换完一圈,边长就减 2 。直到边长小于等于 0 ,就结束。

代码:

public void rotate(int[][] matrix) {
int temp;
int N = matrix.length;
int boundLength = 0;
int sideLength = N - 1;
int row[] = new int[4];
int col[] = new int[4];
while (sideLength > 0) {
row[0] = boundLength;
col[0] = boundLength;
row[1] = boundLength;
col[1] = N - 1 - boundLength;
row[2] = N - 1 - boundLength;
col[2] = N - 1 - boundLength;
row[3] = N - 1 - boundLength;
col[3] = boundLength;
while (col[0] < sideLength + boundLength) {
temp = matrix[row[0]][col[0]];
// 上到右
matrix[row[0]][col[0]] = matrix[row[3]][col[3]];
// 右到下
matrix[row[3]][col[3]] = matrix[row[2]][col[2]];
// 下到左
matrix[row[2]][col[2]] = matrix[row[1]][col[1]];
// 左到上
matrix[row[1]][col[1]] = temp;
col[0]++;
row[1]++;
col[2]--;
row[3]--;
}
boundLength++;
sideLength -= 2;
}
}