Ответов уже много, и я нашел два, требующих O (1) временной сложности. Алгоритм real O (1) - оставить хранилище массива нетронутым и изменить способ индексации его элементов. Цель в том, что он не потребляет дополнительную память и не требует дополнительного времени для итерации данных.
Повороты на 90, -90 и 180 градусов - это простые преобразования, которые можно выполнять, если вы знаете, сколько строк и столбцов в вашем 2D-массиве; Чтобы повернуть любой вектор на 90 градусов, поменяйте местами оси и отрицайте ось Y. Для -90 градусов поменяйте местами оси и отрицайте ось X. При повороте на 180 градусов обе оси не меняются местами.
Возможны дальнейшие преобразования, такие как зеркальное отражение по горизонтали и / или по вертикали путем независимого отрицания осей.
Это можно сделать, например, через метод доступа. Приведенные ниже примеры являются функциями JavaScript, но концепции в равной степени применимы ко всем языкам.
// Get an array element in column/row order
var getArray2d = function(a, x, y) {
return a[y][x];
};
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2d(arr, i, j);
}
}
console.log(newarr);
// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
var t = x;
x = y;
y = a.length - t - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCW(arr, i, j);
}
}
console.log(newarr);
// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
var t = x;
x = a[0].length - y - 1;
y = t;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCCW(arr, i, j);
}
}
console.log(newarr);
// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
x = a[0].length - x - 1;
y = a.length - y - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2d180(arr, i, j);
}
}
console.log(newarr);
Этот код принимает массив вложенных массивов, где каждый внутренний массив представляет собой строку.
Метод позволяет читать (или записывать) элементы (даже в случайном порядке), как если бы массив был повернут или преобразован. Теперь просто выберите правильную функцию для вызова, вероятно, по ссылке, и все готово!
Концепция может быть расширена для применения преобразований аддитивно (и неразрушающе) через методы доступа. Включая произвольные углы поворота и масштабирования.