2013年08月16日

旋转图片


今天看到一个算法题,题目如下:

一张图像表示成N*N的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。你能原地操作吗?(即不开辟额外的存储空间)

分析

这道题其实很简单,只是看了感觉和打印一个回旋的矩阵一样,需要能仔细的操作下标,估计是在面试时要一把过的要求吧。所以写来练下手了。假设矩阵如下:

1  2  3  4  17         17 18 19 59 20
5  6  7  8  18         4  8  12 42 16
9  10 11 12 19 ----->  3  7  11 41 15 
31 18 41 42 59         2  6  10 18 14
13 14 15 16 20         1  5  9  31 13

方法一

有两种思路,我首先想到了一种操作复杂的思路,就是按照旋转的逻辑来旋转数字,首先是旋转最外围,然后里一层,这样一次下去,下标控制复杂。

void rotate(int a[][col], int n){//n = 5
    int distance = n - 1;
    int i = 0,j = 0;
    int row,col;
    for(i = 0; i < n/2; i++){
        for(j = 0; j < distance; j++){//distance = 4
            int temp = a[i][j+i];//a[0][1]
            a[i][j+i] = a[j+i][i+distance];//a[0][1]=a[1][4];
            a[j+i][i+distance] = a[i+distance][i+distance-j]; // a[1][4] = a[4][3];
            a[i+distance][i+distance-j] = a[i+distance-j][i]; // a[4][3] = a[3][0];
            a[i+distance-j][i] = temp; // a[3][0] = a[0][1];
        }
        distance -= 2;
    }
}

思路简单,直接借鉴于实际旋转的过程,可是下标操作不容易控制。

方法二

方法很巧妙,是从出题者那儿看来的。做了两次旋转。

1  2  3  4  17          1  5  9  31 13           17 18 19 59 20
5  6  7  8  18          2  6  10 18 14           4  8  12 42 16
9  10 11 12 19  ----->  3  7  11 41 15  ----->   3  7  11 41 15 
31 18 41 42 59          4  8  12 42 16           2  6  10 18 14
13 14 15 16 20          17 18 19 59 20           1  5  9  31 13

代码如下:

void rotatev2(int a[][col], int n){
    int i = 0, j = 0;
    for(i=0; i < n; i++){
        for(j=i+1;j < n; j++)
            swap(a[i][j],a[j][i]);
    }

    for(i = 0; i < n/2; i++){
        for(j = 0; j < n; j++){
            swap(a[i][j],a[n-i-1][j]);
        }
    }
}

这个代码更加简洁,清晰,思路更巧妙!

前一篇: 最长递增子序列 后一篇: 蚂蚁蚂蚁