力扣|力扣初级算法-07-数组-旋转图像算法|leetcode|职场和发展|算法

学习目标：本次学习目标为力扣初级算法-数组，其中主要的LC如下：

旋转图像

学习内容：

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

示例1：

文章图片

示例2：

文章图片

说明：
matrix.length == n
matrix[i].length == n
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

解题思路：

解法一：直接转换法
边界问题：输入的数组是空或者null，或者只有一个元素
代码逻辑过程:
- 根据二维数组元素的旋转规律，直接生成一个新的二维数组存放旋转后的数组，同时根据旋转规律，将原有数组元素直接写入到新的二维数组
- 规律： n阶数组中，第 i 行转换为第 n- i 列
负责度分析
- 时间复杂度：O(N^2)，其中 NN 是 \textit{matrix}matrix 的边长。
- 空间复杂度：O(N^2)，
代码实现：

/** * 暴力解决，寻找规律就是：当前第 i 行变成第 n-i 列 */ public void rotate01(int[][] matrix) { int n = matrix.length; int [][] newArray = new int[n][n]; for (int[] ints : matrix) { for (int j = 0; j < n; j++) { newArray[j][n - j - 1] = ints[j]; } } for (int i = 0; i < n; i++) { System.arraycopy(newArray[i], 0, matrix[i], 0, n); } }

解法二：原地旋转
边界问题：输入的数组是空或者null，或者只有一个元素
解题思路：
- 基于不可开辟新的数组空间，需对原数组原地旋转，根据二维数组的多次旋转规律，单次的旋转规律为
  m a t r i x n e w [ c o l ] [ n ? r o w ? 1 ] = m a t r i x [ r o w ] [ c o l ] matrix_{new} [col] [n - row -1] = matrix[row] [col] matrixnew?[col][n?row?1]=matrix[row][col]
  经过四次旋转后则个元素回归到原始位，故可在单次旋转过程中，声明变量 temp 作为存放即将别替换的元素值A，当元素A 被元素B 替换后，根据上述公式算出即将替换B 的元素C ，此时再将元素C 替换元素B，如此再往上递归转到元素D 替换元素C，此时，当经过三次替换之后，最后将 temp的元素替换到元素D。
- 需要主要的是，单次的循环设计到了四个元素的移动，相当于做了对称循环，故总的行数循环数可以减半，而列的循环次数则为 n+1/2,具体原因可参看如下图
  
  文章图片
  
  文章图片
代码逻辑过程：
【力扣|力扣初级算法-07-数组-旋转图像】代码实现：

public void rotate02(int[][] matrix) { int length = matrix.length; for (int i = 0; i < length / 2; i++) { for (int j = 0; j < (length + 1) / 2; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[length - j - 1][i]; matrix[length - j - 1][i] = matrix[length - i - 1][length - j - 1]; matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1]; matrix[j][length - i - 1] = temp; } } }

学习笔记：