每日一题——旋转图像

旋转图像

题目链接

---

方法一：利用辅助数组

通过对示例的观察和分析，我们可以得到这样的结论：

• 对于原数组的下标为i行元素，顺时针旋转九十度后，都变成了下标为（n-1-i）列元素。如图所示：

• 对于原数组的下标为j列元素，顺时针旋转九十度后，都变成了下标为(j)行元素。如图所示：

• 结论：

假设带旋转的元素位置为nums[i][j]，那么顺时针旋转九十度后这个元素的位置就应该是nums[j][n-1-i]

这样想清楚后这题似乎就变得十分简单，但是我们应该想到旋转玩一组数据后，有些数据就会被覆盖，如图：

因此，我们可以再新创建一个临时数组来保存这些旋转后的数据，然后再将新数组的数据覆盖到原数组就可以了。

实现代码

void rotate(int** matrix, int matrixSize, int* matrixColSize){int n = matrixSize;//创建临时数组int **ret = (int**)malloc(sizeof(int*) * (n));for (int i = 0; i < n; i++)ret[i] = (int*)malloc(sizeof(int) * n);//先储存旋转后数组的数据for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)ret[j][n - 1 - i] = matrix[i][j];//实现覆盖for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)matrix[i][j] = ret[i][j];//释放临时数组的空间free(ret);
}

方法二： 原地旋转

我们先来看2 * 2数组顺时针旋转九十度的情形：

我们可以认为旋转过程是这样的：D->A、C->D、B->C、A->B，应该注意执行完D->A后，数据A就被覆盖了，因此我们需要创建一个临时变量来保存数据A，这样，这个旋转过程就变为了temp=A, D->A、C->D、B->C、temp->B

我们将数组扩大，那么由上面的推理可以得到，每经过上面的一轮变换，都可以旋转数组的4个元素：

那么如何将整个数组的元素都旋转，我们只需要取数组左上角1/4的元素，并将这些数据作为旋转起点，依次进行旋转即可：

同时经过分析我们也可以得到，一轮旋转的4个元素的下标变化应该是这样的：

最后，我们应该注意区分n为奇数或偶数的情况：

• 当n为偶数，数组的旋转起始位置（左上角1/4区域）为：

• 当n为奇数，数组的旋转起始位置（左上角1/4区域）为：

因此，当n为奇数或者偶数时，区域的列数都为n/2。当n为偶数时，行数为n/2，n为奇数时，行数为(n+1)/2

实现代码

void rotate(int** matrix, int matrixSize, int* matrixColSize){int n = matrixSize;//确定左上角1/4区域的范围int row = n / 2;int col = (n + 1) / 2;//以左上角1/4区域的每个元素为起点，依次进行旋转for (int i = 0; i < row; i++){for (int j = 0; j < col; 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;}}
}