首页 > 代码库 > 【LeetCode】【Python题解】Rotate Image

【LeetCode】【Python题解】Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:

Could you do this in-place?

我的解法非常简洁,就用了一行代码,就是将给定的matrix重新整合,生成了一个新的matrix返回,所以并不是in-place的解法,但优点是十分的简洁,赏心悦目!

class Solution:
    # @param matrix, a list of lists of integers
    # @return a list of lists of integers
    def rotate(self, matrix):
        return map(lambda x:map(lambda y:y.pop(0),matrix[::-1]),range(len(matrix)))

再分享一个看到的非常帅的解法,这个算法就是in-place的了

#include <algorithm>

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) 
    {
        reverse(matrix.begin(), matrix.end());
        for (unsigned i = 0; i < matrix.size(); ++i)
            for (unsigned j = i+1; j < matrix[i].size(); ++j)
                swap (matrix[i][j], matrix[j][i]);
    }
};

乍一看非常难懂,就感觉只是以矩阵的对角线为轴交换了两边的像素点。其实不是。非常关键的一步是reverse()函数,它将matrix翻转了。如果你在纸上写一个nxn的矩阵(反正我是写下来才明白的),reverse之后相当于是把纸翻转过来,而且不是沿长边翻转,而是沿短边翻转(就是不是翻书那种翻转,而是纵向从底部向上的那种翻转),这样翻转之后最底部一行自然就成了最顶部一行。

第二步就是swap对角线两侧的元素,这样又是一次翻转,这次翻转更复杂一些,是沿矩阵对角线的一次翻转(也可以说是沿纸的对角线)

这时你会发现其实这就是把纸顺时针旋转了90度。

【LeetCode】【Python题解】Rotate Image