RotateImage [source code]
public class RotateImage {
static
/******************************************************************************/
class Solution {
public void rotate(int[][] matrix) {
int N = matrix.length, cube_len = (N + 1) / 2;
for (int i = 0; i < cube_len; i++) {
for (int j = 0; j < N - cube_len; j++) {
Point[] points = new Point[4];
points[0] = new Point (i, j);
points[1] = new Point (j, N - 1 - i);
points[2] = new Point (N - 1 - i, N - 1 - j);
points[3] = new Point (N - 1 - j, i);
for (int k = 3; k >= 1; k--)
swap (matrix, points[k], points[k - 1]);
}
}
}
void swap (int[][] matrix, Point A, Point B) {
int tmp = matrix[A.x][A.y];
matrix[A.x][A.y] = matrix[B.x][B.y];
matrix[B.x][B.y] = tmp;
}
static class Point {
int x, y;
Point (int x, int y) {this.x = x; this.y = y;}
}
}
/******************************************************************************/
public static void main(String[] args) {
RotateImage.Solution tester = new RotateImage.Solution();
int[][][] inputs = {
{
{1,2,3},
{4,5,6},
{7,8,9}
},
{
{7,4,1},
{8,5,2},
{9,6,3}
}, // 1
{
{ 5, 1, 9,11},
{ 2, 4, 8,10},
{13, 3, 6, 7},
{15,14,12,16}
},
{
{15,13, 2, 5},
{14, 3, 4, 1},
{12, 6, 8, 9},
{16, 7,10,11},
}, // 2
};
for (int i = 0; i < inputs.length / 2; i++) {
int[][] matrix = inputs[2 * i];
String input_str = Matrix.printMatrix (matrix);
System.out.println (Printer.separator ());
tester.rotate (matrix);
String output_str = Matrix.printMatrix (matrix), ans_str = Matrix.printMatrix (inputs[2 * i + 1]);
System.out.printf ("%s -> \n%s, expected: \n%s\n",
input_str, Printer.wrapColor (output_str, output_str.equals (ans_str) ? "green" : "red"), ans_str
);
}
}
}
感觉难点一个是确定组成rotate的最小单元, 在边长是奇数和偶数的情况下, 怎么选择一个小的rotate单元, 让计算好处理; 另外一个难点就是单元选好之后的坐标计算;
另外, 这题的空间要求也有点迷, 说是不允许额外allocate, 那么实际上到底最后允许的额外空间是多少? 比如我把一个rotate单元的cube都cache下来, 行不行?
最后我想想还是用单个cell的swap来写了; 计算的过程通过例子来启发; 这个题目当中充分认识到V2上面一个C语言大神的观点, 记忆算法, 关键还是要记忆trace; 比如我下面的这个trace里面, 当你写出来1,4,16,13 -> 13,1,4,16之后, 算法直接就很明显了;
不过上面这个例子也有坏处, 一开始看这个例子, 以为只要找到关于中心的点对称位置就行了, 事实上这样算出来的结果是不对的;
刚开始不知道这里的旋转坐标应该怎么计算, 后来相同了: i和j不过是相对于matrix的边缘的offset, 所以计算其他的旋转点的坐标的时候, 好好利用这个不变的offset就行了;
最后超时才写出来, 很丢人, 速度是3ms (13%). 不过好歹最后写出来的代码还算简洁;
这个是当时思考的时候打的草稿:
总体来说这个题目还是比较tricky的, 看起来思路很简单, 做一个简单的事情, 但是实际上背后的计算还是很难的; 对于rotate的理解要求深刻, 比如, 实际上一个cube是cube_len * (N - cube_len), 我一开始以为是cube_len * cube_len, 这些都是需要掌握的概念, 以及旋转点坐标的计算, 上面也讲了;
没有editorial;
@shichaotan said in A common method to rotate the image:
here give a common method to solve the image rotation problems.
// clockwise rotate
// first reverse up to down, then swap the symmetry
// 1 2 3 7 8 9 7 4 1
// 4 5 6 => 4 5 6 => 8 5 2
// 7 8 9 1 2 3 9 6 3
void rotate(vector<vector<int> > &matrix) {
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
// anticlockwise rotate
// first reverse left to right, then swap the symmetry
// 1 2 3 3 2 1 3 6 9
// 4 5 6 => 6 5 4 => 2 5 8
// 7 8 9 9 8 7 1 4 7
void anti_rotate(vector<vector<int> > &matrix) {
for (auto vi : matrix) reverse(vi.begin(), vi.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
原来rotate问题是有套路的, 可以学习一下; 另外, 注意他的swap symmetry这一步的写法, 可以学习一下; 另外他这个对称性, 说的其实害死关于主对角线的对称性, 你可以看到, 主对角线在第二步之后是没有改变的;
java版本, 没什么特别的:
@Jerry said in A common method to rotate the image:
Java Code
public void rotate(int[][] matrix) {
int s = 0, e = matrix.length - 1;
while(s < e){
int[] temp = matrix[s];
matrix[s] = matrix[e];
matrix[e] = temp;
s++; e--;
}
for(int i = 0; i < matrix.length; i++){
for(int j = i+1; j < matrix[i].length; j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
@erhart said in [A common method to rotate the image](https://discuss.leetcode.com/post/160979):
> It's a good method, but remember this is a high school geometry level problem. All rotations are composite reflections (in fact, all transformations are composite reflections); in this case, a reflection across the vertical line of symmetry, then a reflection across the diagonal. If you recall this fact, this method will allow you to swap in-place rather than having to endure the tedium of multiplying by a rotation matrix.
>
> Don't forget your maths, kids!
等于说这个其实是他们高中教过的; 看看也不错, 学习了;
对于逆时针, 有人给出了另外一个更加节省的做法:
@qeatzy said in [A common method to rotate the image](https://discuss.leetcode.com/post/173750):
> anti_rotate() could reverse only once too. just reverse after transpose instead.
>
```c++
void anti_rotate(vector<vector<int> > &matrix) {
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
reverse(matrix.begin(), matrix.end());
}
脑子很活;
@LuckyIdiot said in AC Java in place solution with explanation Easy to understand.:
The idea was firstly transpose the matrix and then flip it symmetrically. For instance,
1 2 3 4 5 6 7 8 9after transpose, it will be swap(matrix[i][j], matrix[j][i])
1 4 7 2 5 8 3 6 9Then flip the matrix horizontally. (swap(matrix[i][j], matrix[i][matrix.length-1-j])
7 4 1 8 5 2 9 6 3Hope this helps.
```java
public class Solution {
public void rotate(int[][] matrix) {
for(int i = 0; i<matrix.length; i++){
for(int j = i; j<matrix[0].length; j++){
int temp = 0;
temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for(int i =0 ; i<matrix.length; i++){
for(int j = 0; j<matrix.length/2; j++){
int temp = 0;
temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length-1-j];
matrix[i][matrix.length-1-j] = temp;
}
}
}
}
跟上个解法的评论里面看到的做法是类似的, reverse放到第二步;
@dxy93 said in [AC Java in place solution with explanation Easy to understand\.](https://discuss.leetcode.com/post/92211):
> We can transpose the matrix as follows.
>
```java
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
这里才发现上面看算法的时候没有仔细看, 当然, 这个东西本身倒不是很难理解, 这个其实就是一个三角形循环, 如果你自己把i,j的范围iterate走一遍的话(3x3的矩阵就可以了). 反正要熟悉一下就行了;
@bupt_zhaorui said in AC Java in place solution with explanation Easy to understand.:
public void rotate(int[][] matrix) {
int n = matrix.length;
int tmp;
for(int i = 0; i < Math.ceil((double)n/2); i++){
for(int j = i; j < n - 1 - i; j ++){
tmp = matrix[i][j];
matrix[i][j] = matrix[n-1-j][i];
matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
matrix[j][n-1-i] = tmp;
}
}
}
这个其实就跟我的做法是类似的了;
@kunkkawei said in AC Java in place solution with explanation Easy to understand.:
The first loop can be done in one dimension loop:
```java
public class Solution {
public void rotate(int[][] matrix) {
int len = matrix.length;
for(int i = 0; i < len / 2; i++) {
int[] tmp = matrix[i];
matrix[i] = matrix[len - 1 - i];
matrix[len - 1 - i] = tmp;
}
for(int i = 0; i < len; i++) {
for(int j = 0; j < i; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
}
}
上下reverse确实比左右reverse要好写一些;
---
Stefan总结了一些Python的写法:
@StefanPochmann said in [Seven Short Solutions \(1 to 7 lines\)](https://discuss.leetcode.com/post/16980):
> While these solutions are Python, I think they're understandable/interesting for non-Python coders as well. But before I begin: No mathematician would call a matrix `matrix`, so I'll use the usual `A`. Also, btw, the 40 ms reached by two of the solutions is I think the fastest achieved by Python solutions so far.
>
> ---
>
> **Most Pythonic - `[::-1]` and `zip`** - 44 ms
>
> The most pythonic solution is a simple one-liner using `[::-1]` to flip the matrix upside down and then `zip` to transpose it. It assigns the result back into `A`, so it's "in-place" in a sense and the OJ accepts it as such, though some people might not.
>
> class Solution:
> def rotate(self, A):
> A[:] = zip(*A[::-1])
>
> ---
>
> **Most Direct** - 52 ms
>
> A 100% in-place solution. It even reads and writes each matrix element only once and doesn't even use an extra temporary variable to hold them. It walks over the *"top-left quadrant"* of the matrix and directly rotates each element with the three corresponding elements in the other three quadrants. Note that I'm moving the four elements in parallel and that `[~i]` is way nicer than `[n-1-i]`.
>
> class Solution:
> def rotate(self, A):
> n = len(A)
> for i in range(n/2):
> for j in range(n-n/2):
> A[i][j], A[~j][i], A[~i][~j], A[j][~i] = \
> A[~j][i], A[~i][~j], A[j][~i], A[i][j]
>
> ---
>
> **Clean Most Pythonic** - 56 ms
>
> While the OJ accepts the above solution, the the result rows are actually tuples, not lists, so it's a bit dirty. To fix this, we can just apply `list` to every row:
>
> class Solution:
> def rotate(self, A):
> A[:] = map(list, zip(*A[::-1]))
>
> ---
>
> **List Comprehension** - 60 ms
>
> If you don't like `zip`, you can use a nested list comprehension instead:
>
> class Solution:
> def rotate(self, A):
> A[:] = [[row[i] for row in A[::-1]] for i in range(len(A))]
>
> ---
>
> **Almost as Direct** - 40 ms
>
> If you don't like the little repetitive code of the above "Most Direct" solution, we can instead do each four-cycle of elements by using three swaps of just two elements.
>
> class Solution:
> def rotate(self, A):
> n = len(A)
> for i in range(n/2):
> for j in range(n-n/2):
> for _ in '123':
> A[i][j], A[~j][i], i, j = A[~j][i], A[i][j], ~j, ~i
> i = ~j
>
> ---
>
> **Flip Flip** - 40 ms
>
> Basically the same as the first solution, but using `reverse` instead of `[::-1]` and transposing the matrix with loops instead of `zip`. It's 100% in-place, just instead of only moving elements around, it also moves the rows around.
>
> class Solution:
> def rotate(self, A):
> A.reverse()
> for i in range(len(A)):
> for j in range(i):
> A[i][j], A[j][i] = A[j][i], A[i][j]
>
> ---
>
> **Flip Flip, all by myself** - 48 ms
>
> Similar again, but I first transpose and then flip left-right instead of upside-down, and do it all by myself in loops. This one is 100% in-place again in the sense of just moving the elements.
>
> class Solution:
> def rotate(self, A):
> n = len(A)
> for i in range(n):
> for j in range(i):
> A[i][j], A[j][i] = A[j][i], A[i][j]
> for row in A:
> for j in range(n/2):
> row[j], row[~j] = row[~j], row[j]
后面有空再看了, 感觉就是一些对Python语法的利用; 反正我现在也不熟悉Python, 无所谓了; 另外, 帖子里面Stefan后来还给了很多评论和解释, 可能需要点进去看一下;
---
@baifriend said in [Clear Java solution](https://discuss.leetcode.com/post/21897):
```java
public class Solution {
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;
}
}
}
好像这个也行:
@fengdianzhang said in Clear Java solution:
基本一模一样，不过我的用这个：
for(int i=0; i < ( n + 1 ) / 2; i++) for(int j=0; j < n / 2; j++)反正取矩阵的四分之一就行了。
discussion基本没有其他的解法了, 一个就是reflection的做法, 一个就是我这种计算rotate的做法; submission基本波动;
另外, 一张我后面贴在discussion上面用来解释我自己的思路的图:
Problem Description
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
- You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
Difficulty:Medium
Total Accepted:148.2K
Total Submissions:361.4K
Contributor:LeetCode
Companies
microsoftamazonapple
Related Topics
array