[第二轮] 2/18-2/24 CareerCup 1.6

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

暂时没时间写长的，先用python偷懒写一种简短的解法上来
#a is image data,for example [[1,2,3],[4,5,6],[7,8,9]],d indicate the direction you want to rotate the image to,d=0 is right,other is left
def rotate(a,d):
    if d==0:
        return [[x[i] for x in a[::-1]] for i in range(len(a))]
    else:
        return [[x[i] for x in a] for i in range(len(a),-1,-1)]

rotate to left by 90 degrees in two steps :
1. flip vertically
2. transpose the matrix (swap m [row][col] and m[col][row])
Time complexity O(N), N is the number of pixel.

https://gist.github.com/Zuohr/4972470

rotate by layer, loop from outside edges to inside ones

https://gist.github.com/chrislukkk/4973845

zuohr 发表于 2013-2-18 01:44
rotate to left by 90 degrees in two steps :
1. flip vertically
2. tranpose the matrix (swap m [row ...

Nice job! In your solution, you decompose rotation into two simpler operation on matrix: flip and transposition. And your algorithm gives us a 90 degree rotation in counterclockwise direction. My algorithm is similar to you, but in clockwise direction

grassgigi 发表于 2013-2-18 06:43
rotate by layer, loop from outside edges to inside ones

https://gist.github.com/chrislukkk/497384 ...

Wow, another cool idea!Your algorithm will run faster than mine and zuohr's on large input since you only need to run 1 nested loop. But maybe for someone it seems a little hard to comprehend. when implementing, we should pay more attention to the swap order. But still, it is a nice algorithm

https://gist.github.com/cqx83/4974220
矩阵中相应的4个位置，a[i][j]，a[j][n-i-1]，a[n-i-1][n-j-1]，a[n-j-1][i]swap一次，矩阵中每个元素都被traverse一次，O(N^2)，N为每行的元素数

by doing the swap with :
matx[ i][i][j]-> temp,
matx[n-j-1][i] ->matx[i][j],
matx[n-i-1][n-j-1] ->matx[n-j-1][i],
matx[j][n-i-1] -> matx[n-i-1][n-j-1],
temp -> matx[j][n-i-1]
https://gist.github.com/mazl123321/4974405[/i][/i][/i][/i]

clockwise direction , switch from outside to inside
https://gist.github.com/calmcaicai/4983593

At first turn 180 degree, and then turn through back-diagonal.
https://github.com/Tedatworking/ ... ster/20130217_6.cpp