【leetcode】48 Rotate Image

发表于 | 分类于 ，


描述

旋转一个二维数组，不能创建另外的二维数组来复制。

样例

样例1

1
2
3
4
5
6
7
8
9
10
11
12
输入:
     [
       [1,2,3],
       [4,5,6],
       [7,8,9]
     ],
输出:
     [
       [7,4,1],
       [8,5,2],
       [9,6,3]
     ]

样例2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入:
     [
       [ 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]
     ]

思路

我们先考虑简单的，假设只有四个数字，怎么处理？显然循环的交换，基于这个想法，可以把这个二维数组分为四个部分，然后找到要交换的对象就 ok 了， 在下面算法中，其实交换 4 个值的函数可以直接写在循环里面，减少不必要的运算。

代码

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
26
class Solution {
private:
    void swap4Value(vector<vector<int>>& matrix ,int idx1,int idx2,int idx3,int idx4){
        int size = matrix.size();
        int temp = matrix[idx1/size][idx1%size];
        matrix[idx1/size][idx1%size] = matrix[idx4/size][idx4%size];
        matrix[idx4/size][idx4%size] = matrix[idx3/size][idx3%size];
        matrix[idx3/size][idx3%size] = matrix[idx2/size][idx2%size];
        matrix[idx2/size][idx2%size] = temp;
    }

public:
    void rotate(vector<vector<int>>& matrix) {
        int size = matrix.size();
        for(int row =0; row < (matrix.size() + 1)/2;row ++){
            for(int col = 0;col <matrix.size()/2;col ++){
                swap4Value(matrix,
                    row*size+col,
                    col * size + size - 1 - row,
                    (size-1 -row) *size + size -1 -col,
                    (size-1 - col) *size + row
                    );
            }
        }
    }
};

参考

原题链接