[数据结构与算法]Leetcode-找规律题

q48 旋转图像

题目传送门

题解

这道题要求不能使用额外的数组，不然就是一道简单题，官方题解给了两种可行的做法：

1. 原地旋转数组：
   通过分析我们可以发现，原来在a[i][j]的元素经过旋转以后，位置就变成了a[j][n - i - 1]，所以我们就得到了以下的等式：a[j][n - i - 1] = a[i][j]；根据这个性质我们不难推出，a[j][n - i - 1]所在的元素，经过旋转以后，位置就变成了a[n - i - 1][n - j - 1]，进而得到等式：a[n - i - 1][n - j - 1] = a[j][n - i - 1]；而a[n - i - 1][n - j - 1]位置的元素旋转以后位置就变成了a[n - j - 1][i]，得到等式：a[n - j - 1][i] = a[n - i - 1][n - j - 1]；a[n - j - 1][i]位置的元素旋转以后又变回了a[i][j]，得到等式：a[i][j] = a[n - j - 1][i]。现在元素位置的改变成为了一个闭环，接着每次循环，我们就可以一次性对四个位置的值做一次变换，刚好符合题目的要求。
   但是我们还有一个问题：如何确定循环的次数？其实很简单，因为我们每循环一次就要改变四个位置的元素，所以当n为偶数时需要循环(n ^ 2) / 4 = (n / 2) * (n / 2)次；当n为奇数时需要循环(n ^ 2 - 1) / 4 = ((n - 1) / 2) * ((n + 1) / 2)次。

   func rotate(matrix [][]int)  {
   	n := len(matrix)
   	for i := 0; i < n / 2; i++ {
   		for j := 0; j < (n + 1) / 2; j++ {
   			matrix[i][j], matrix[j][n - i - 1], matrix[n - i - 1][n - j - 1], matrix[n - j - 1][i] =
   				matrix[n - j - 1][i], matrix[i][j], matrix[j][n - i - 1], matrix[n - i - 1][n - j - 1]
   		}
   	}
   }
   

2. 转化为转置数组求解：

   我们可以先将数组进行水平翻转，经过水平翻转以后我们可以发现，目标数组与水平翻转以后的数组只差转置这一个步骤。

   func rotate(matrix [][]int) {
   	n := len(matrix)
   	// 水平翻转
   	for i := 0; i < n / 2; i++ {
   		for j := 0; j < n; j++ {
   			matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
   		}
   	}
   	// 转置
   	for i := 0; i < n; i++ {
   		for j := 0; j < i; j++ {
   			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
   		}
   	}
   	fmt.Println(matrix)
   }