順時針旋轉矩陣
目錄
- 一、問題描述
- 二、解題思路
- 1. 原地旋轉矩陣
- 2. 旋轉邏輯
- 3. 代碼實現
- 三、代碼解析
- 1. 參數說明
- 2. 原地旋轉邏輯
- 3. 返回矩陣
- 四、示例測試代碼
- 五、復雜度分析
- 1. 時間復雜度
- 2. 空間復雜度
一、問題描述
以下是內容轉換為 CSDN 的 Markdown 格式：
問題描述
給定一個 N * N\的整數矩陣，請編寫一個算法將其順時針旋轉 90 度。旋轉后的矩陣需要返回。例如，給定矩陣：
1 2 3
4 5 6
7 8 9
旋轉 90 度后應變為：
7 4 1
8 5 2
9 6 3
說明
- 矩陣的旋轉操作是原地進行的，即不額外分配空間。
- 示例中的矩陣旋轉后，行和列的值發生了相應的變化。
數據范圍
- (0 < n < 300)
- 矩陣中的值滿足 (0 \leq val \leq 1000)
復雜度要求
- 空間復雜度：(O(1))
- 時間復雜度：(O(N^2))
二、解題思路
1. 原地旋轉矩陣
為了滿足空間復雜度 (O(1)) 的要求，我們需要在原矩陣上直接進行操作，而不是使用額外的空間。具體步驟如下：
- 分層旋轉：矩陣可以分為多層，每一層從外到內逐步旋轉。
- 旋轉步驟：
- 保存左上角的值。
- 按順時針方向依次交換四個位置的值。
2. 旋轉邏輯
對于每個元素 ((i, j))，其旋轉后的位置可以通過以下公式計算：
- 新行索引 (i’ = j)
- 新列索引 (j’ = N - i - 1)
3. 代碼實現
以下是完整的C語言實現代碼，包含詳細的注釋：
#include <stdio.h>
#include <stdlib.h>/*** 順時針旋轉矩陣90度* @param mat: 輸入矩陣* @param matRowLen: 矩陣的行數* @param matColLen: 矩陣的列數（每行的長度）* @param n: 矩陣的階數（n x n）* @param returnSize: 返回矩陣的行數* @param returnColumnSizes: 返回矩陣的列數（每行的長度）* @return: 旋轉后的矩陣*/
int** rotateMatrix(int** mat, int matRowLen, int* matColLen, int n,int* returnSize, int** returnColumnSizes) {// 設置返回矩陣的行數和列數*returnSize = n; // 設置返回矩陣的行數為n*returnColumnSizes = (int*)malloc(n * sizeof(int)); // 分配內存用于存儲每行的列數for (int i = 0; i < n; i++) {(*returnColumnSizes)[i] = n; // 每行的列數也為n}// 原地旋轉矩陣for (int layer = 0; layer < n / 2; layer++) { // 遍歷每一層，從外層到內層int first = layer; // 當前層的起始索引int last = n - layer - 1; // 當前層的結束索引for (int i = first; i < last; i++) { // 遍歷當前層的每個元素int gap = i - first; // 當前元素與起始索引的偏移量int temp = mat[first][i]; // 保存左上角的值// 左上 <- 左下mat[first][i] = mat[last - gap][first];// 左下 <- 右下mat[last - gap][first] = mat[last][last - gap];// 右下 <- 右上mat[last][last - gap] = mat[i][last];// 右上 <- 左上（保存的值）mat[i][last] = temp;}}// 返回原地旋轉后的矩陣return mat;
}
三、代碼解析
1. 參數說明
mat：輸入的二維矩陣。matRowLen：矩陣的行數。matColLen：矩陣的列數（每行的長度）。n：矩陣的階數（矩陣是 (n \times n) 的）。returnSize：返回矩陣的行數（通過指針返回）。returnColumnSizes：返回矩陣的列數（每行的長度，通過指針返回）。
2. 原地旋轉邏輯
- 分層旋轉：矩陣可以分為多層，每一層從外到內逐步旋轉。
- 旋轉步驟：
- 保存左上角的值：將左上角的值保存到臨時變量
temp。 - 左上 <- 左下：將左下角的值移動到左上角。
- 左下 <- 右下：將右下角的值移動到左下角。
- 右下 <- 右上：將右上角的值移動到右下角。
- 右上 <- 左上（保存的值）：將保存的左上角的值移動到右上角。
- 保存左上角的值：將左上角的值保存到臨時變量
3. 返回矩陣
- 設置返回矩陣的行數和列數：
*returnSize = n：返回矩陣的行數。*returnColumnSizes：返回矩陣的列數（每行的長度）。
- 返回原地旋轉后的矩陣
mat。
四、示例測試代碼
以下是測試代碼，用于驗證 rotateMatrix 函數的正確性：
#include <stdio.h>int main() {int n = 3;int mat[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};int* matPtr[3];for (int i = 0; i < n; i++) {matPtr[i] = mat[i];}int returnSize;int* returnColumnSizes;int** rotated = rotateMatrix(matPtr, n, NULL, n, &returnSize, &returnColumnSizes);printf("Rotated Matrix:\n");for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {printf("%d ", rotated[i][j]);}printf("\n");}free(returnColumnSizes);return 0;
}
輸出
輸入：
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], 3
輸出：
Rotated Matrix:
7 4 1
8 5 2
9 6 3
五、復雜度分析
1. 時間復雜度
- 每個元素只被訪問一次，時間復雜度為 (O(N^2))。
2. 空間復雜度
- 除了輸入矩陣外，沒有使用額外的空間，空間復雜度為 (O(1))。
)
