rotate 2D array （rotate image）升级版 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

rotate 2D array （rotate image）升级版

rotate 2D array （rotate image）升级版# JobHunting - 待字闺中

d*r2015-04-21 07:04

1 楼

3 pounds small package from South to MI $16.7 with $500 insurance. Alsomost
double as FedEx.
Also does $500 insurance with UPS include free signature?

h*t2015-04-21 07:04

2 楼

电面，碰到传说中的“国人大哥”，上来考了rotate array (leetcode 原题)，很快搞
定。接着说要出一个2D array rotation问题，当时还庆幸又是原题（rotate image）
，大哥不错啊，知道放水。
接着听就不对劲了。不是90度旋转，而是要把每一个element都顺时针移动 k steps。
比如n = 5, k = 3,
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
变为
16 11 6 1 2
21 18 17 12 3
22 19 13 7 4
23 14 9 8 5
24 25 20 15 10
本来想这两道题一起出，我就用一下rotate array的程序吧，就是把每一个circle的
element取出来放到一个Array里，rotate完了，再放回去，但大哥说复杂度太高。再想
，，，
那就只有用rotate image的思路了，一个个挪，时间O(n*n),空间O(1)。
思路对了，接着写程序，才发现没那么简单，而且时间也快到了。
跪了。。。。
电话完了，接着写（google了，网上没查到有这个题），最后总算搞定了，才发现里面
还有90旋转，180旋转的情况，继续改。
，，，，，
完全搞完，花了我几个小时。
，，，
大哥，就那么点时间，你要我搞定这个！！！

h*a2015-04-21 07:04

3 楼

no

Alsomost

【在 d*****r 的大作中提到】

: 3 pounds small package from South to MI $16.7 with $500 insurance. Alsomost
: double as FedEx.
: Also does $500 insurance with UPS include free signature?

B*12015-04-21 07:04

4 楼

跪了。

d*r2015-04-21 07:04

5 楼

thanks!

e*72015-04-21 07:04

6 楼

好可怕

n*n2015-04-21 07:04

7 楼

本质上还是一维啊，一圈一圈走。就是数组下标映射一下。怎么觉得这个比二维的简单。
刷题刷到见题就套，有点走火入魔。

【在 h***t 的大作中提到】

: 电面，碰到传说中的“国人大哥”，上来考了rotate array (leetcode 原题)，很快搞
: 定。接着说要出一个2D array rotation问题，当时还庆幸又是原题（rotate image）
: ，大哥不错啊，知道放水。
: 接着听就不对劲了。不是90度旋转，而是要把每一个element都顺时针移动 k steps。
: 比如n = 5, k = 3,
: 1 2 3 4 5
: 6 7 8 9 10
: 11 12 13 14 15
: 16 17 18 19 20
: 21 22 23 24 25

z*m2015-04-21 07:04

8 楼

最烦这种无聊的题，

s*e2015-04-21 07:04

9 楼

如果要求空间最小，是只需要一个element的空间啊。
把第一个数字取出来，然后算逆时针k steps，看是谁要放到第一个空出来的位置上，
放过去后第二个位置空出来了，然后再计算逆时针k steps，把第3个数字放到第二个空
出来的位置上。。。直到全部move了一遍后，然后再同样对内圈操作。

E*12015-04-21 07:04

10 楼

这个题b格够高的

【在 h***t 的大作中提到】

s*x2015-04-21 07:04

11 楼

这题我在Amazon也见到了，跪了。

w*n2015-04-21 07:04

12 楼

傻逼国人大哥！操国人大哥！

n*u2015-04-21 07:04

13 楼

好像就是1D array rotate加个转圈就行了吧？转圈那个确实有点麻烦。
一共有n/2个圈要转。
试着把每个圈都铺平了，当linked list一样做rotate，也就是写个新的self.next()
function。
大概这样？
for offset in range(0, n/2):
# do while loop in python
x = offset
y = offset
while True:
# rotate x, y, by k steps
# 记不得怎么写rotate list的懒人路过
(x, y) = get_next(n, x, y, offset)
if x == y:
#回到出发点结束
break
# rotation 的 self.next() function。
# offset can be calculated with n, x, y, but it'll be available anyways.
def get_next(n, x, y, offset):
if x == n - offset :
if y == n - offset :
return x-1, y
else:
return x, y+1
elif x == offset :
if y == offset:
return x+1, y
else:
return x, y-1
else:
if y == n - offset :
return x-1, y
else: # y offset
return x+1, y

p*r2015-04-21 07:04

14 楼

不用这么麻烦，按照圈打印出来matrix（Spiral Matrix）那个题会吧，
这里就是把每圈的index加个K然后对于圈长取余算出来新坐标再放回去就行了

【在 n*********u 的大作中提到】

: 好像就是1D array rotate加个转圈就行了吧？转圈那个确实有点麻烦。
: 一共有n/2个圈要转。
: 试着把每个圈都铺平了，当linked list一样做rotate，也就是写个新的self.next()
: function。
: 大概这样？
: for offset in range(0, n/2):
: # do while loop in python
: x = offset
: y = offset
: while True:

x*02015-04-21 07:04

15 楼

mark

Z*02015-04-21 07:04

16 楼

怎么这两天都是类似的题目。

b*w2015-04-21 07:04

17 楼

def rotate_by_k(matrix, k):
i = 0
while i < len(matrix)>>1:
# construct 1-d array
nums = []
x, y = i, i
while x < len(matrix) - i - 1:
nums.append(matrix[y][x])
x += 1

while y < len(matrix) - i - 1:
nums.append(matrix[y][x])
y += 1
while x > i:
nums.append(matrix[y][x])
x -= 1
while y > i:
nums.append(matrix[y][x])
y -= 1

k %= len(nums)
nums = nums[::-1]
nums = nums[k-1::-1] + nums[-1:k-1:-1]
x, y, s = i, i, 0
while x < len(matrix) - i - 1:
matrix[y][x] = nums[s]
x += 1
s += 1
while y < len(matrix) -i -1:
matrix[y][x] = nums[s]
y += 1
s += 1

while x > i:
matrix[y][x] = nums[s]
x -= 1
s += 1
while y > i:
matrix[y][x] = nums[s]
y -= 1
s += 1
i += 1

b*w2015-04-21 07:04

18 楼

贴了个代码在楼上，　把值取出来ｒｏｔａｔｅ就可以了

l*s2015-04-21 07:04

19 楼

private void rotateImage(int[,] board, int k)
{
int m = board.GetLength(0), n = board.GetLength(1);
int cycleM = m, cycleN = n;
while(cycleM > 1)
{
int oX = (m - cycleM) / 2, oY = (n - cycleN) / 2;
int[] xy = new int[2] { oX, oY };
int tmp = board[xy[0], xy[1]];
int[] nextXY = getNextXY(xy, m, n, cycleM, cycleN, k);
while(nextXY[0] != oX || nextXY[1] != oY)
{
tmp = tmp ^ board[nextXY[0], nextXY[1]] ^ (board[nextXY[0],
nextXY[1]] = tmp);
nextXY = getNextXY(nextXY, m, n, cycleM, cycleN, k);
}
board[oX, oY] = tmp;
cycleM -= 2;
cycleN -= 2;
}
}
private int[] getNextXY(int[] xy, int boardM, int boardN, int cycleM, int
cycleN, int k)
{
int minX = (boardM - cycleM) / 2, minY = (boardN - cycleN) / 2;
int maxX = minX + cycleM - 1, maxY = minY + cycleN - 1;
int[] newXY = new int[2] { xy[0], xy[1] };
k %= 2 * (cycleM + cycleN - 2); // If K is greater than 1 full cycle,
limit it in 1 cycle
if (k >= cycleM + cycleN - 2) // If K is greater than half a full
cycle, rotate half a cycle
{
newXY = new int[2] { boardM - xy[0] - 1, boardN - xy[1] - 1 };
k -= cycleM + cycleN - 2;
}
//Craw the edge step by step in half a cycle
while(k-- > 0)
if (newXY[0] == minX && newXY[1] != maxY) newXY[1]++;
else if (newXY[1] == maxY && newXY[0] != maxX) newXY[0]++;
else if (newXY[0] == maxX && newXY[1] != minY) newXY[1]--;
else if (newXY[1] == minY && newXY[0] != minX) newXY[0]--;
return newXY;
}

f*e2015-04-21 07:04

20 楼

原题写起来也很烦。

c*g2015-04-21 07:04

21 楼

傻逼国人大哥，hhh

a*82015-04-21 07:04

22 楼

Java version:
public static void rotateMatrix(int[][] matrix,int k) {

if(matrix==null||matrix.length==0||matrix[0].length==0||matrix.
length!=matrix[0].length)

return ;

if(matrix.length==1)

return;

if(k<=0)

return;

int m = matrix.length/2;

for(int i = 0;i
helper(matrix,i,k,4*(matrix.length-2*i)-4);
}

}
private static void helper(int[][] matrix,int i,int k,int length) {

k = k%length;

if(k==0)

return;

int reach = length;

int sideLength = (length+4)/4;

for(int m=0;m
int[] temp_xy = getXY(m,i,sideLength,matrix.length);

int temp = matrix[temp_xy[0]][temp_xy[1]];

int n = m;

while((n-k+length)%length!=m) {

int key = (n-k+length)%length;

temp_xy = getXY(n,i,sideLength,matrix.length);

int[] new_xy = getXY(key,i,sideLength,matrix.length);

matrix[temp_xy[0]][temp_xy[1]] = matrix[new_xy[0]][new_xy[1]
];

n = key;

reach = Math.min(reach, n);

}

temp_xy = getXY(n,i,sideLength,matrix.length);

matrix[temp_xy[0]][temp_xy[1]] = temp;

}

}
private static int[] getXY(int m,int i,int sideLength,int lengthOfMatrix) {

int[] res = new int[2];

switch(m/(sideLength-1)) {

case 0:
res[0] = i;
res[1] = i+m%(sideLength-1);
return res;

case 1:

res[0] = i+m%(sideLength-1);
res[1] = lengthOfMatrix-1-i;
return res;

case 2:

res[0] = lengthOfMatrix-1-i;
res[1] = lengthOfMatrix-1-i-m%(sideLength-1);
return res;

case 3:

res[0] = lengthOfMatrix-1-i-m%(sideLength-1);
res[1] = i;
return res;

default:

return res;

}
}