刷题笔记:力扣第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)已经是最优解。