Rotate Array

Q: Co się stanie, gdy k będzie większe niż długość tablicy?

Co n kroków tablica wraca do początkowego układu, więc znaczenie ma tylko k mod n kroków. Obrócenie [10, 20, 30] o 7 kroków daje ten sam efekt co obrócenie jej o 1 krok, co daje [30, 10, 20] . Gdy k jest wielokrotnością n , tablica się nie zmienia.

Q: Jak obrócić tablicę w lewo?

Obrót w lewo o k to obrót w prawo o n - (k mod n) . Przy użyciu odwracania odwróć pierwsze k mod n wartości, następnie pozostałe, a na końcu całą tablicę. W obu przypadkach czas działania wynosi O(n).

ŚrednieTablice i napisy Dwa wskaźniki

+10

Otrzymujesz tablicę liczb całkowitych nums oraz liczbę k. Obróć tablicę w prawo o k kroków: w jednym kroku każda wartość przesuwa się o jedno miejsce w prawo, a ostatnia wartość zawija się na początek. Zwróć obróconą tablicę.

k może być znacznie większe niż długość tablicy.

Funkcja

rotate(nums: integer-array, k: integer) → integer-array

numsinteger-array: tablica liczb całkowitych do obrócenia
kinteger: o ile kroków obrócić w prawo
Zwracainteger-array: tablica nums przesunięta w prawo o k pozycji

Ograniczenia

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ k ≤ 10⁹

Przykłady

Wejście: nums = [4, 9, 1, 6, 3]k = 2
Wyjście: [6, 3, 4, 9, 1]
Wyjaśnienie: Dwa kroki w prawo przenoszą dwie ostatnie wartości, 6 i 3, na początek. Pozostałe trzy wartości przesuwają się o dwa miejsca w prawo i zachowują swoją kolejność: [6, 3, 4, 9, 1].

Pytanie dodatkowe

Czy możesz obracać tablicę w miejscu, przenosząc każdą wartość bezpośrednio do (i + k) mod n i przenosząc dalej wartość, którą zastąpi? Ile cykli to tworzy?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Co każde n kroków tablica wraca do stanu początkowego, więc najpierw zredukuj k, które może wynosić 10^9, do k mod n. Następnie zapisz każdą wartość bezpośrednio pod jej końcowym indeksem w drugiej tablicy albo uzyskaj ten sam rezultat w tej tablicy za pomocą trzech odwróceń i dodatkowej pamięci O(1).

Skopiuj każdą wartość na jej nowy indeks

Intuicja

Po k krokach wartość na indeksie i znajduje się pod indeksem (i + k) mod n, więc zapisz ją bezpośrednio w tym miejscu, bez wykonywania tych kroków. Najpierw zredukuj k do k mod n: obrót o n przywraca każdą wartość na jej poprzednie miejsce, więc gdy k = 7 i n = 3, pozostaje tylko jeden krok.

Jedno przejście umieszcza wszystkie n wartości: czas O(n) oraz pamięć O(n) na wynik. W ten sposób nie możesz zapisywać bezpośrednio do nums, ponieważ każdy zapis nadpisałby wartość, której jeszcze nie przeniesiono.

Algorytm

Ustaw n na długość nums i zastąp k przez k mod n.
Utwórz tablicę wynikową o długości n.
Dla każdego indeksu i zapisz nums[i] pod indeksem result[(i + k) mod n].
Zwróć wynik.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

Trzy odwrócenia na miejscu

Intuicja

Podziel tablicę na A, pierwsze n-k wartości, oraz B, ostatnie k wartości. Obrócona tablica to B, po której następuje A, przy czym każdy blok zachowuje swoją pierwotną kolejność. Odwrócenie całej tablicy zmienia kolejność bloków i kolejność elementów wewnątrz każdego z nich, więc B jest pierwsze, ale ma odwróconą kolejność, podobnie jak A. Ponowne odwrócenie każdego bloku przywraca pierwotną kolejność jego elementów.

Dla [4, 9, 1, 6, 3] i k = 2: odwrócenie wszystkiego daje [3, 6, 1, 9, 4], odwrócenie pierwszych dwóch elementów daje [6, 3, 1, 9, 4], a odwrócenie ostatnich trzech daje [6, 3, 4, 9, 1].

Każda wartość jest zamieniana miejscami najwyżej dwa razy, więc czas działania wynosi O(n), a dodatkowa pamięć obejmuje kilka zmiennych indeksowych (O(n) w R, które kopiuje wektor, gdy funkcja pomocnicza odwracająca go zmienia).

Algorytm

Ustaw n na długość nums i zastąp k przez k mod n.
Odwróć całą tablicę, indeksy od 0 do n-1.
Odwróć pierwszy blok, indeksy od 0 do k-1.
Odwróć drugi blok, indeksy od k do n-1.
Zwróć nums.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing

    def reverse(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    reverse(0, n - 1)  # the last k values come to the front, backwards
    reverse(0, k - 1)  # put the front block back in order
    reverse(k, n - 1)  # and the back block
    return nums

Pułapki i przypadki brzegowe

Pomijanie k mod n. Przy k = 10^9 obracanie krok po kroku nigdy się nie kończy, a odwrócenie pierwszych k wartości powoduje odczyt daleko poza końcem tablicy.
Wycinkowanie bez modulo. W Pythonie nums[-k:] + nums[:-k] przy k = 7 i n = 3 zwraca niezmienioną tablicę, ponieważ oba wycinki kończą się na krawędzi tablicy.
Odwracanie w niewłaściwej kolejności. Odwrócenie najpierw dwóch bloków, a na końcu całej tablicy, daje rotację w lewo.
Błąd o jeden na granicy bloku: pierwszy blok kończy się na indeksie k-1, a drugi zaczyna się od k. W Lua i R, w których indeksowanie zaczyna się od 1, bloki to 1..k i k+1..n.

Najczęstsze pytania3

Jaka jest złożoność czasowa algorytmu Rotate Array?

O(n) zarówno dla podejścia z kopiowaniem, jak i trzech odwróceń, ponieważ każda wartość jest przenoszona stałą liczbę razy. Najpierw zredukowanie k za pomocą k mod n sprawia, że duża wartość k nie ma znaczenia. Obracanie o jeden krok naraz kosztuje za to O(n × k).

Co się stanie, gdy k będzie większe niż długość tablicy?

Co n kroków tablica wraca do początkowego układu, więc znaczenie ma tylko k mod n kroków. Obrócenie [10, 20, 30] o 7 kroków daje ten sam efekt co obrócenie jej o 1 krok, co daje [30, 10, 20]. Gdy k jest wielokrotnością n, tablica się nie zmienia.

Jak obrócić tablicę w lewo?

Obrót w lewo o k to obrót w prawo o n - (k mod n). Przy użyciu odwracania odwróć pierwsze k mod n wartości, następnie pozostałe, a na końcu całą tablicę. W obu przypadkach czas działania wynosi O(n).

def rotate(nums, k):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

nums = [4, 9, 1, 6, 3]
k = 2

Oczekiwany wynik

[6, 3, 4, 9, 1]