Es gibt bereits viele Antworten, und ich habe zwei gefunden, die eine Zeitkomplexität von O(1) angeben. Die real O(1)-Algorithmus besteht darin, den Array-Speicher unangetastet zu lassen und die Indizierung der Elemente zu ändern. Das Ziel dabei ist, dass weder zusätzlicher Speicherplatz noch zusätzliche Zeit für die Iteration der Daten benötigt wird.
Drehungen um 90, -90 und 180 Grad sind einfache Transformationen, die durchgeführt werden können, wenn Sie wissen, wie viele Zeilen und Spalten Ihr 2D-Array hat. Um einen beliebigen Vektor um 90 Grad zu drehen, vertauschen Sie die Achsen und negieren die Y-Achse. Für -90 Grad vertauschen Sie die Achsen und negieren die X-Achse. Für 180 Grad negieren Sie beide Achsen, ohne sie zu vertauschen.
Weitere Transformationen sind möglich, z. B. eine horizontale und/oder vertikale Spiegelung durch unabhängige Negierung der Achsen.
Dies kann z. B. durch eine Accessor-Methode geschehen. Bei den folgenden Beispielen handelt es sich um JavaScript-Funktionen, aber die Konzepte gelten für alle Sprachen gleichermaßen.
// 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);
Dieser Code geht von einem Array aus verschachtelten Arrays aus, wobei jedes innere Array eine Zeile ist.
Mit dieser Methode können Sie Elemente (auch in zufälliger Reihenfolge) lesen (oder schreiben), als ob das Array gedreht oder transformiert worden wäre. Jetzt müssen Sie nur noch die richtige Funktion zum Aufrufen auswählen, wahrscheinlich per Referenz, und schon kann es losgehen!
Das Konzept kann erweitert werden, um Transformationen additiv (und nicht-destruktiv) über die Accessor-Methoden anzuwenden. Einschließlich beliebiger Winkeldrehungen und Skalierungen.
