数据结构与算法-1 ：旋转图像

石璞东

发布于 2020-05-22 15:02:04

6700

发布于 2020-05-22 15:02:04

文章被收录于专栏：石璞东 | haha石璞东 | haha

全文字数：1794字

全文配图：4 图

全文阅读时间：5min

前言

从本文开始，我将开启一个新的系列文章的编写数据结构与算法，在本系列文章中，我将对牛客、LeetCode等主流算法刷题平台的精彩题目进行讲解，实现语言包括Python（主）、Javascript、C、C++，同时我也会将相关算法与我们的实际开发项目结合，帮助大家更好的理解这略显枯燥的算法。

【LeetCode】题目描述

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例1：

给定 matrix =
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],
原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2：

给定 matrix =
[
  [ 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]
]

思路提供

01 - 矩阵旋转示意图

观察转化前后的矩阵对应元素，不难发现：

图1.1 数字翻转示意图

图1.2 数字翻转示意图

图1.3 数字翻转示意图

图1.4 数字翻转示意图

02 - 总结思路

用arr代表二维数组 i、j 表示数组对应下标，替换过程为 :

记录当前元素 tmp=arr[0][0]
顺时针开始逐一替换
- arr[0][0]=arr[3][0]
- arr[3][0]=arr[3][3]
- arr[3][3]=arr[0][3]
- arr[0][3]=tmp

进而将这种情况推广到一般状态下即为 :

tmp = arr[i][j]
matrix[i][j] = matrix[n-1-j][i]
matrix[n-1-j][i] = matrix[n-1-i][n-1-j]
matrix[n-1-i][n-1-j] = matrix[j][n-1-i]
matrix[j][n-1-i] = temp

03 - 结论

观察变化前后的数组可知 , 先将数组的行进行翻转 , 然后再求翻转后矩阵的转置矩阵即可。

代码展示

Python

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

C++

class Solution {
  public:
      void rotate(vector<vector<int>>& matrix) {
          unsigned int n = matrix.size();
          for(unsigned int i = 0; i < n/2; ++i){
              for(unsigned int j = i; j < n - 1 - i; ++j){
                  int temp = matrix[i][j];
                  matrix[i][j] = matrix[n-1-j][i];
                  matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                  matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                  matrix[j][n-1-i] = temp;
              }
          }
      }
  };

本文总结

在本文中，我们通过简单的几个示意图讲解了如何对一个四阶矩阵进行原地（顺时针）旋转，并通过分析矩阵中的元素位置，将元素一般替换过程推广到普适的替换过程，最终得出本题的思路，我们最后还通过Python、C++对这个题目进行了实现，小伙伴们学会了吗？快去实现一下吧！