Постановка задачи
Вам предоставляется n x n 2D матрица, представляющая изображение, поверните изображение на 90 градусов (по часовой стрелке).
Вы должны повернуть изображение на месте, что означает, что вам нужно напрямую изменить входную 2D-матрицу. НЕ выделяйте другую 2D-матрицу и выполняйте вращение.
Описание проблемы взято из: https://leetcode.com/problems/rotate-image
Пример 1:
Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Пример 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]]
Пример 3:
Input: matrix = [[1]]
Output: [[1]]
Пример 4:
Input: matrix = [[1, 2], [3, 4]]
Output: [[3, 1], [4, 2]]
Ограничения:
- matrix.length == n
- matrix[i].length == n
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
Объяснение
Поворот групп из четырех ячеек
Первое решение, которое мы можем придумать, - повернуть четыре угла матрицы. Мы повторяем это и для последующих ячеек.
Давайте проверим алгоритм.
- 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
Временная сложность программы составляет O (M), поскольку каждая ячейка считывается один раз и записывается один раз. Сложность пространства равна O (1), потому что мы не используем никаких других дополнительных структур данных.
Решение 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;
}
}
}
};
Решение 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;
}
}
}
Решение 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;
}
}
};
Давайте проверим наш алгоритм, чтобы увидеть, как работает решение.
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]]
Первоначально опубликовано на https://alkeshghorpade.me.