Algorytmy i struktury danych · Middle · Pytanie 74 z 75
Jak obrócić tablicę w prawo o k pozycji w miejscu z O(1) dodatkowej pamięci?
// [1, 2, 3, 4, 5, 6, 7], k = 3 -> [5, 6, 7, 1, 2, 3, 4]- 1Wywołać
arr.unshift(arr.pop())k razy w pętli - ✓Poprawna odpowiedź: Odwrócić całą tablicę, potem odwrócić pierwsze k i resztę
- 3Skopiować ostatnie k elementów do nowej tablicy i połączyć
Wyjaśnienie
Trzy odwrócenia stawiają każdy element na miejscu w czasie O(n) i z O(1) pamięci. unshift(pop()) to O(n) na krok, czyli łącznie O(n × k), a kopiowanie wymaga O(n) pamięci. Dla k większego od długości użyj k % n.