Алгоритми та структури даних · Middle · Запитання 74 з 75
Як циклічно зсунути масив праворуч на k позицій на місці з O(1) додаткової пам'яті?
// [1, 2, 3, 4, 5, 6, 7], k = 3 -> [5, 6, 7, 1, 2, 3, 4]- 1Викликати
arr.unshift(arr.pop())k разів у циклі - ✓Правильна відповідь: Розвернути весь масив, потім розвернути перші k і решту
- 3Скопіювати останні k елементів у новий масив і склеїти
Пояснення
Три розвороти ставлять кожен елемент на місце за O(n) часу й O(1) пам'яті. unshift(pop()) коштує O(n) на крок, тобто O(n × k) загалом, а копіювання потребує O(n) пам'яті. Для k, більших за довжину, використовуйте k % n.