Skip to content

Latest commit

 

History

History
181 lines (126 loc) · 3.9 KB

0048._rotate_image.md

File metadata and controls

181 lines (126 loc) · 3.9 KB

48. Rotate Image

难度: Medium

刷题内容

原题连接

内容描述

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

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

解题方案

思路 1 - 时间复杂度: O(row * col)- 空间复杂度: O(1)******

先将矩阵上下翻转，然后将矩阵沿主对角线（即左上到右下）中心对称翻转，即可实现顺时针90度旋转。

  • 上下翻转规律 [i][:] --> [n-1-i][:]
  • 对角线变换的规律是 [i][j] --> [j][i]

例如：

1 1 1    3 3 3    3 2 1
2 2 2 -> 2 2 2 -> 3 2 1
3 3 3    1 1 1    3 2 1

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        # 上下翻转
        for i in range(n/2):
            matrix[i], matrix[n-1-i] = matrix[n-1-i], matrix[i]
        # 主对角线翻转
        for i in range(n):
            for j in range(i+1,n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

思路 2 - 时间复杂度: O(row * col)- 空间复杂度: O(1)******

参考这里

http://www.lifeincode.net/programming/leetcode-rotate-image-java/

找规律，一次完成四个数的该有的变换


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

在思路一的解法下观察得出，每个元素的变换是 [x][y] -> [n-1-x][y] -> [y][n-1-x] -> [n-1-y][x]

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(n/2):
            for j in range(n-n/2):
                matrix[i][j], matrix[~j][i], matrix[~i][~j], matrix[j][~i] = \
                         matrix[~j][i], matrix[~i][~j], matrix[j][~i], matrix[i][j]

这里的[~i] 意思就是 [n-1-i]

思路 3 - 时间复杂度: O(row * col)- 空间复杂度: O(1)******

分层翻转，从最外层翻转，一直翻转到最里面一层，参考Bittiger

beats 94.49%

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        def rotateOneLayer(layer):
            size = len(matrix)
            for i in range(layer, len(matrix)-1-layer):
                matrix[layer][i], matrix[i][size-1-layer], matrix[size-1-layer][size-1-i], matrix[size-1-i][layer] = \
                matrix[size-1-i][layer], matrix[layer][i], matrix[i][size-1-layer], matrix[size-1-layer][size-1-i]
            
        for layer in range((len(matrix)+1)/2):
            rotateOneLayer(layer)

思路 4 - 时间复杂度: O(row * col)- 空间复杂度: O(1)******

直接用zip函数，一行, 😂

class Solution:
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        matrix[:] = zip(*matrix[::-1])