Rotate Array

Q: Che cosa succede quando k è maggiore della lunghezza dell’array?

Ogni n passaggi riportano l’array all’ordine iniziale, quindi contano solo k mod n passaggi. Ruotare [10, 20, 30] di 7 è come ruotarlo di 1, ottenendo [30, 10, 20] . Quando k è un multiplo di n , l’array non cambia.

Q: Come si ruota un array verso sinistra?

Una rotazione a sinistra di k è una rotazione a destra di n - (k mod n) . Con le inversioni, inverti i primi k mod n valori, poi il resto e infine l'intero array. Entrambi i metodi richiedono un tempo O(n).

MedioArray e stringhe Due puntatori

+10

Hai un array di numeri interi nums e un numero k. Ruota l'array verso destra di k passi: a ogni passo, ogni valore si sposta di una posizione verso destra e l'ultimo valore torna in testa. Restituisci l'array ruotato.

k può essere molto più grande della lunghezza dell'array.

Funzione

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

numsinteger-array: l'array di interi da ruotare
kinteger: quanti passi ruotare verso destra
Restituisceinteger-array: nums ruotato a destra di k posizioni

Vincoli

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

Esempi

Input: nums = [4, 9, 1, 6, 3]k = 2
Output: [6, 3, 4, 9, 1]
Spiegazione: Due passi verso destra portano in testa gli ultimi due valori, 6 e 3. Gli altri tre valori si spostano di due posizioni a destra e mantengono il loro ordine: [6, 3, 4, 9, 1].

Per approfondire

Puoi ruotare sul posto spostando ogni valore direttamente in (i + k) mod n e continuando con il valore che sposta? Quanti cicli si formano?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ogni n passi riportano l’array al punto di partenza, quindi prima riduci k, che può essere 10^9, a k mod n. Poi scrivi ogni valore direttamente al suo indice finale in un secondo array, oppure ottieni lo stesso risultato all’interno dell’array con tre inversioni e O(1) memoria aggiuntiva.

Copia ogni valore nel suo nuovo indice

Intuizione

Dopo k passaggi, il valore all’indice i si trova in (i + k) mod n, quindi scrivilo direttamente lì senza eseguire i passaggi. Riduci prima k a k mod n: una rotazione di n riporta ogni valore nella posizione iniziale, quindi con k = 7 e n = 3 resta un solo passaggio.

Un’unica iterazione posiziona tutti gli n valori: tempo O(n), più memoria O(n) per il risultato. Non puoi scrivere direttamente in nums in questo modo, perché ogni scrittura sovrascriverebbe un valore che non hai ancora spostato.

Algoritmo

Imposta n alla lunghezza di nums e sostituisci k con k mod n.
Crea un array risultato di lunghezza n.
Per ogni indice i, memorizza nums[i] in result[(i + k) mod n].
Restituisci il risultato.

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

Tre inversioni sul posto

Intuizione

Dividi l'array in A, i primi n-k valori, e B, gli ultimi k. L'array ruotato è B seguito da A, ciascun blocco nel suo ordine originale. Invertire l'intero array capovolge sia l'ordine dei blocchi sia l'ordine all'interno di ciascuno, quindi B viene prima ma è al contrario, e lo stesso vale per A. Invertendo di nuovo ciascun blocco se ne ripristina l'ordine interno.

Per [4, 9, 1, 6, 3] e k = 2: invertendo tutto si ottiene [3, 6, 1, 9, 4], invertendo i primi due si ottiene [6, 3, 1, 9, 4] e invertendo gli ultimi tre si ottiene [6, 3, 4, 9, 1].

Ogni valore viene scambiato al massimo due volte, quindi il tempo è O(n) e la memoria aggiuntiva è costituita da alcune variabili indice (O(n) in R, che copia il vettore quando la funzione helper di inversione lo modifica).

Algoritmo

Imposta n alla lunghezza di nums e sostituisci k con k mod n.
Inverti l'intero array, dagli indici 0 a n-1.
Inverti il primo blocco, dagli indici 0 a k-1.
Inverti il secondo blocco, dagli indici k a n-1.
Restituisci 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

Trappole e casi limite

Dimenticare k mod n. Con k = 10^9, ruotare passo dopo passo non finisce mai, e invertire i primi k valori legge ben oltre la fine dell'array.
Suddividere senza usare il modulo. In Python, nums[-k:] + nums[:-k] con k = 7 e n = 3 restituisce l'array invariato, perché entrambe le sezioni si fermano al limite dell'array.
Invertire nell'ordine sbagliato. Invertire prima i due blocchi e per ultimo l'intero array produce una rotazione a sinistra.
Errore di un'unità al limite del blocco: il primo blocco termina all'indice k-1 e il secondo inizia da k. In Lua e R, che contano a partire da 1, i blocchi sono 1..k e k+1..n.

Domande frequenti3

Qual è la complessità temporale di Rotate Array?

O(n) sia per l’approccio con copia sia per le tre inversioni, perché ogni valore viene spostato un numero costante di volte. Ridurre prima k con k mod n impedisce che un k enorme abbia importanza. Ruotare di un passo alla volta costa invece O(n × k).

Che cosa succede quando k è maggiore della lunghezza dell’array?

Ogni n passaggi riportano l’array all’ordine iniziale, quindi contano solo k mod n passaggi. Ruotare [10, 20, 30] di 7 è come ruotarlo di 1, ottenendo [30, 10, 20]. Quando k è un multiplo di n, l’array non cambia.

Come si ruota un array verso sinistra?

Una rotazione a sinistra di k è una rotazione a destra di n - (k mod n). Con le inversioni, inverti i primi k mod n valori, poi il resto e infine l'intero array. Entrambi i metodi richiedono un tempo O(n).

def rotate(nums, k):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

[6, 3, 4, 9, 1]