Vấn đề

Bạn được cấp một nxn 2D ma trận đại diện cho một hình ảnh, xoay hình ảnh bằng cách 90 độ (theo chiều kim đồng hồ).

Bạn phải xoay hình ảnh tại chỗ, điều đó có nghĩa là bạn phải sửa đổi trực tiếp ma trận 2D đầu vào. KHÔNG phân bổ một ma trận 2D khác và thực hiện phép quay.

Câu hỏi được lấy từ: https://leetcode.com/problems/rotate-image

Ví dụ 1:

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Ví dụ 2:

Input: matrix = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
Output: [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

Ví dụ 3:

Input: matrix = [[1]]
Output: [[1]]

Ví dụ 4:

Input: matrix = [[1, 2], [3, 4]]
Output: [[3, 1], [4, 2]]

Hạn chế:

- matrix.length == n
- matrix[i].length == n
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000

Giải thích

Xoay nhóm bốn ô

Giải pháp đầu tiên chúng ta có thể nghĩ đến là xoay bốn góc của ma trận. Chúng tôi cũng lặp lại điều này với các ô tiếp theo.

Hãy kiểm tra thuật toán.

- initialize m = matrix.size, tmp
- loop for i = 0; i < m / 2; i++
- loop for j = i; j < m - 1 - i; j++
- tmp = matrix[i][j]
- matrix[i][j] = matrix[m - 1 - j][i]
- matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]
- matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]
- matrix[j][m - 1 - i] = tmp

Độ phức tạp về thời gian của chương trình là O(M) vì mỗi ô sẽ được đọc một lần và được viết một lần. Độ phức tạp của không gian là ồ(1) bởi vì chúng tôi không sử dụng bất kỳ cấu trúc dữ liệu bổ sung nào khác.

giải pháp C++

class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int m = matrix.size(), tmp;
int j = 0;
for(int i = 0; i < m/2; i++){
for(int j = i; j < m - 1 - i; j++){
tmp = matrix[i][j];
matrix[i][j] = matrix[m - 1 - j][i];
matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];
matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];
matrix[j][m - 1 - i] = tmp;
}
}
}
};

Giải pháp Golang

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

Giải pháp Javascript

var rotate = function(matrix) {
let m = matrix.length;
let tmp = 0;
let i, j;
for(i = 0; i < m/2; i++){
for(j = i; j < m - 1 - i; j++){
tmp = matrix[i][j];
matrix[i][j] = matrix[m - 1 - j][i];
matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];
matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];
matrix[j][m - 1 - i] = tmp;
}
}
};

Chạy khô

Hãy chạy thử thuật toán của chúng tôi để xem giải pháp hoạt động như thế nào.

Input:
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Step 1: m = matrix.length
m = 3
Step 2: tmp = 0
Step 3: loop i = 0; i < 3/2
0 < 3/2
0 < 1
true
j = i; j < 3 - 1 - 0
0 < 2
true
tmp = matrix[i][j]
tmp = 1
matrix[i][j] = matrix[m - 1 - j][i]
matrix[0][0] = matrix[3 - 1 - 0][0]
matrix[0][0] = matrix[2][0]
matrix[0][0] = 7
matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]
matrix[3 - 1 - 0][0] = matrix[3 - 1 - 0][3 - 1 - 0]
matrix[2][0] = matrix[2][2]
matrix[2][0] = 9
matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]
matrix[3 - 1 - 0][3 - 1 - 0] = matrix[0][3 - 1 - 0]
matrix[2][2] = matrix[0][2]
matrix[2][2] = 3
matrix[j][m - 1 - i] = tmp
matrix[0][3 - 1 - 0] = 1
matrix[0][2] = 1
j++
j = 1
Step 4: j < 2
1 < 2
true
tmp = matrix[0][1]
tmp = 2
matrix[i][1] = matrix[m - 1 - j][i]
matrix[0][1] = matrix[3 - 1 - 1][0]
matrix[0][1] = matrix[1][0]
matrix[0][1] = 4
matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - 1]
matrix[3 - 1 - 1][0] = matrix[3 - 1 - 0][3 - 1 - 1]
matrix[1][0] = matrix[2][1]
matrix[1][0] = 8
matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]
matrix[3 - 1 - 0][3 - 1 - 1] = matrix[1][3 - 1 - 0]
matrix[2][1] = matrix[1][2]
matrix[2][1] = 6
matrix[1][m - 1 - i] = tmp
matrix[1][3 - 1 - 0] = 1
matrix[1][2] = 2
j++
j = 2
Step 5: j < 2
2 < 2
false
Step 6: i++
i = 1
1 < 3/2
1 < 1
false
Output:
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]