刷题笔记:力扣第48题-旋转图像

1.拿到这道题目，第一反应是再创建一个新的矩阵，按照顺时针旋转90°的方式遍历原来的矩阵，将旋转后的矩阵存入新矩阵中，输出即可。这种方法的时间复杂度和空间复杂度均为O(n2)。

2.但本题不允许使用新的矩阵，这意味着一切修改就只能在原矩阵上进行，而且不能是简单地使用交换，因为并不是简单的遍历矩阵进行两两位置交换就可旋转整个矩阵。那么只能是覆写，为了保证每次覆写之后不丢失原来的值，可以让下次旋转的对象就是本次被覆写的值。

3.发现按照如上思想进行覆写，每次覆写都会经历固定四次循环就会结束，即四个元素为一组形成了一个覆写环，如下图所示：

4.假定从矩阵左上角开始遍历，即(0, 0)，发现想要遍历所有覆写环只需要如下代码即可：

1. for (row = 0; row < matrixSize / 2; row++){ 2. for (col = row; col < (*matrixColSize) - 1 - row; col++){ 3. // 覆写实现相关代码 4. } 5. }

只需要遍历前一半的行数，每一行需要遍历到每行“末尾角标减去行数”个元素。具体逻辑为从外向内将矩阵分割为一圈又一圈的正方形，每一行的最后一个元素都不需要遍历，因为四个角就是一个覆写环，最后一个元素也在本层正方形上，已经被覆写替换了。而每向下一行，上一行的边界（即外层正方形）都已经被覆写了，内层正方形就不需要管外层的元素了，所以额外减去行数。

5.最后要解决的是如何进行覆写？想到可以用数学中有关三角函数的公式来计算，设覆写元素坐标为(x1, y1)，被覆写元素坐标为(x2, y2)，顺时针旋转90°在坐标轴上即角度减去90°，可得关系式：x2 = y1, y2 = -x1。

6.继续进行推导，假定为n * n的矩阵，矩阵旋转中心可以看做是(n/2, n/2)，而x1到y轴的距离等于y2到x轴的距离，具体如下图所示：

则x1 – n/2 = n/2 – y2，可以推导出：y2 = n – 1 – x1。

7.基于以上思想，初步写出的代码如下：

1. void rotate(int** matrix, int matrixSize, int* matrixColSize) { 2. int row, col, tmp; 3. for (row = 0; row < matrixSize / 2; row++){ 4. for (col = row; col < (*matrixColSize) - 1 - row; col++){ 5. int i = row, j = col, tmp = matrix[i][j]; 6. for (int num = 0; num < 4; num++){ 7. if (num != 3){ 8. matrix[i][j] = matrix[j][matrixSize - 1 - i]; 9. } else { 10. matrix[i][j] = tmp; 11. break; 12. } 13. int k = i; 14. i = j; 15. j = matrixSize - 1 - k; 16. } 17. } 18. } 19. }

但是本地测试报错了，报错如下：

8.发现最后输出变成了逆时针旋转90°的结果，思考之后得知虽然是顺时针覆写，但我代码的逻辑应该是每次寻找下一个未覆写的元素，去覆写上一次执行覆写的元素，所以每次坐标变换应该是寻找下一个逆时针旋转的元素！于是关系式就变为了：x2 = n – 1 – y1, y2 = x1。

修正后的代码如下：

1. void rotate(int** matrix, int matrixSize, int* matrixColSize) { 2. int row, col, tmp; 3. // ========== 外层循环：按「层」遍历矩阵（从外到内） ========== 4. // matrixSize/2：只处理前半层，内层无需旋转（如3×3只处理第0层，4×4处理0/1层） 5. for (row = 0; row < matrixSize / 2; row++){ 6. // ========== 中层循环：遍历当前层的「上边」元素 ========== 7. // col从row开始：避免重复处理左上角元素 8. // col < (*matrixColSize)-1-row：只遍历当前层上边的有效元素（不包含最后一个，避免重复） 9. for (col = row; col < (*matrixColSize) - 1 - row; col++){ 10. // 1. 保存当前元素（旋转的起点值，最后一步填回） 11. int i = row, j = col, tmp = matrix[i][j]; 12. // 2. 内层循环：四个位置顺时针循环交换（核心） 13. // 循环4次：前3次赋值，第4次填回初始值 14. for (int num = 0; num < 4; num++){ 15. if (num != 3){ 16. // 关键：当前位置 = 顺时针旋转前的上一个位置的值，即逆时针旋转90°的位置 17. // 坐标变换公式：(i,j) 接收 (matrixSize-1-j, i) 的值 18. matrix[i][j] = matrix[matrixSize - 1 - j][i]; 19. } else { 20. // 第4次循环：把初始保存的tmp填回最后一个位置，完成闭环 21. matrix[i][j] = tmp; 22. break; // 交换完成，退出内层循环 23. } 24. // 3. 坐标更新：跳转到下一个要赋值的位置（实际为逆时针旋转90°的坐标变换） 25. int k = j; // 保存旧的j值，避免被覆盖 26. j = i; // 新j = 旧i 27. i = matrixSize - 1 - k; // 新i = 矩阵边长-1 - 旧j 28. } 29. } 30. } 31. }

本次通过了，时间复杂度为O(n2)，空间复杂度为O(1)，已经是最优解。