Skip to content

Latest commit

 

History

History
 
 

048.Rotate-Image

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

048.Rotate-Image

解法1

将整个方阵分为四个象限。可以想象,将整个方阵瞬时间旋转90度,就等于将各个象限关于坐标原点旋转90度。特别需要注意到,四个象限分别有一个点,这四个点在旋转过程中是彼此重合的。我们以4*4的方阵为例:对于左下角的坐标A(0,1),对应的左上角的位置是B(1,0),右上角的位置是C(2,3),右下角的位置是D(3,2).我们如果将方阵旋转一周,这四个点的元素会分别变成B,C,D,A。

所以我们只要遍历一个象限中的所有点,让每个点调整它在四个象限中对应的位置即可。比如说在第一象限中的(x,y),旋转后在下一个象限中的位置就是(N-1-y,x)。我们将象限I与II交换,再把II与III交换,再把III与IV交换,注意通过三次交换,而不是四次,即可将这四个点形成旋转90的效果。举个例子:ABCD->BACD->BCAD->BCDA.

对于N为奇数的情况,除了四个象限外,还多出四个对称的坐标轴不属于任何象限。我们可以将四个坐标轴分别归给每个象限,这样就不用再单独对它们做处理了。所以外层循环的框架对于i和j遍历范围是略微不同的:

for (int i=0; i<N/2; i++)
  for (int j=0; j<(N+1)/2; j++)
     ...

解法2

有一个更容易记忆的方法,分两步走。对于形如 [A,B;D,C]的方针,我们先上下翻转,得到[D,C;A,B]。然后我们对这个方针求转置,得到的是[D',A';C',B'],而这个恰好就是原方阵顺时针旋转90度的结果。

Leetcode Link