Algorithmen und Datenstrukturen · Middle · Frage 74 von 75
Wie rotiert man ein Array an Ort und Stelle um k Positionen nach rechts, mit O(1) zusätzlichem Speicher?
// [1, 2, 3, 4, 5, 6, 7], k = 3 -> [5, 6, 7, 1, 2, 3, 4]- 1k-mal in einer Schleife
arr.unshift(arr.pop())aufrufen - 2Das ganze Array umdrehen, dann die ersten k und den Rest umdrehen
- 3Die letzten k Elemente in ein neues Array kopieren und verketten
Antwort zeigen
Richtige Antwort: Das ganze Array umdrehen, dann die ersten k und den Rest umdrehen
Erklärung
Drei Umkehrungen bringen jedes Element in O(n) Zeit und O(1) Speicher an seinen Platz. unshift(pop()) ist O(n) pro Schritt, insgesamt also O(n × k), und Kopieren braucht O(n) Speicher. Nutze k % n, wenn k größer als die Länge ist.