048 Rotate image

Original Description: 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.


  • 要求: 给一个 N X N 的矩阵,顺时针旋转90度

  • 返回: 旋转后的 NXN 矩阵

  • 例子:
    • input:
      [[1,2,3],
      [4,5,6],
      [7,8,9]],
    • output:
      [[7,4,1],
      [8,5,2],
      [9,6,3]]

Solution

  • \(i\)为当前行,\(j\)为当前列。
  • 一个元素的替换:
    1. 先将 \(m[i][j]\)放入stack, i.e. stack[0] = \(m[i][j]\)
    2. 原本在 \(m[i][j]\) 位置的数字会跑到\(m[j][N-1-i]\) 的位置上去。所以将\(m[j][N-1-i]\)位置的元素也压入stack。
    3. 将\(m[j][N-1-i]\) 用 stack[0]替换,stack pop。
    4. 更新当前的行,列位置为\(j\),\(N-1-i\).
  • inner loop: 由于矩阵有四条边,所以需要进行上述替换4次。
  • outer loop: 对第i行, 我们只需要从元素\(m[i][i]\)(对角线上的元素) 开始替换,到\(m[i][N-1-i]\) 结束(从最外圈向最内圈)。
  • class Solution(object):
    def rotate(self, m):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
            
        d = len(m)
        def update(m, i,j, tmp): 
            tmp.append(m[j][d-1-i])
            m[j][d-1-i] = tmp[0]
            ip = j
            jp = d-1-i
            tmp.pop(0)
            return m, ip, jp, tmp
    
        for i in range(d//2):
            for j in range(i,d-1-i):
                tmp = [m[i][j]]
                count = 0
                # need 4 times to update on each side of the matrix
                while count < 4:
                    m,i,j, tmp = update(m,i,j,tmp)
                    count += 1