Leaders in an Array

+10

Ti viene fornito un array di numeri interi nums. Un elemento è un leader quando è maggiore o uguale a ogni elemento alla sua destra. L'ultimo elemento non ha nulla alla sua destra, quindi è sempre un leader. Restituisci tutti i leader, nell'ordine in cui compaiono in nums da sinistra a destra.

Funzione

leaders(nums: integer-array) → integer-array

numsinteger-array: l’array di interi in cui cercare
Restituisceinteger-array: i leader di nums, da sinistra a destra

Vincoli

1 ≤ nums.length ≤ 25000
-10⁹ ≤ nums[i] ≤ 10⁹

Esempi

Input: nums = [12, 5, 9, 3, 6, 2]
Output: [12, 9, 6, 2]
Spiegazione: 2 è l’ultimo, quindi è in testa. 6 batte il 2 che lo segue, 9 batte 3, 6 e 2, e 12 batte tutti. 5 perde contro 9 e 3 perde contro 6, quindi la risposta è [12, 9, 6, 2].

Per approfondire

Se i valori arrivano uno alla volta e dopo ciascuno devi comunicare i leader finora, come aggiorni la lista in tempo O(1) ammortizzato per valore?

Suggerimenti

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

0 di 3 aperti

Soluzione

Leggi da sinistra: ogni elemento richiede una nuova scansione del suffisso. Procedi invece da destra: l’unica cosa che devi sapere sul suffisso è il suo valore massimo, e basta una variabile per contenerlo. In questo modo, un controllo O(n²) diventa un’unica passata.

Controlla tutto ciò che si trova a destra

Corretto, ma non termina sui test più grandi

Intuizione

Applica la definizione: per ogni indice i, esamina gli elementi successivi e fermati al primo strettamente maggiore di nums[i]. Se l’esame arriva alla fine, nums[i] è un leader. Verifichi gli indici da sinistra a destra, quindi i leader risultano in ordine. In [12, 5, 9, 3, 6, 2], 5 si ferma a 9 e 3 si ferma a 6.

Il costo sta nelle scansioni che arrivano fino alla fine. Con 24,999 valori uguali seguiti da un valore più grande, ogni elemento percorre quasi tutto l’array: circa 25,000 × 25,000 / 2, oltre 3 × 10^8 confronti.

Algoritmo

Crea un elenco dei risultati vuoto.
Per ogni indice i, scorri j da i + 1 fino alla fine.
Se qualche nums[j] è maggiore di nums[i], fermati: nums[i] non è un leader.
Se non esiste un j del genere, aggiungi nums[i] al risultato.
Restituisci il risultato.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

Una sola scansione da destra mantenendo il massimo corrente

Intuizione

Essere almeno grande quanto ogni elemento a destra equivale a essere almeno grande quanto il loro massimo. Procedendo da destra verso sinistra, puoi mantenere aggiornato quel massimo. L'ultimo elemento è dominante e dà inizio al massimo. Ogni elemento alla sua sinistra è dominante quando è almeno pari al massimo, e allora diventa il nuovo massimo; altrimenti, alla sua destra c'è un valore più grande.

Con [12, 5, 9, 3, 6, 2]: 2 è dominante, poi 6, poi 9, poi 12, mentre 3 e 5 sono inferiori al massimo. Hai trovato [2, 6, 9, 12]; invertita, questa è la risposta.

Ogni elemento viene confrontato una volta: tempo O(n) e spazio aggiuntivo O(1), oltre al risultato. La versione R contrassegna gli elementi dominanti in un vettore logical(n), quindi il suo spazio aggiuntivo è O(n).

Algoritmo

Inserisci l’ultimo elemento nel risultato e imposta best a quel valore.
Sposta i dall’indice penultimo fino a 0.
Se nums[i] ≥ best, aggiungi nums[i] al risultato e imposta best a quel valore.
Inverti il risultato in modo che gli elementi massimi si leggano da sinistra a destra e restituiscilo.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Trappole e casi limite

Usare > invece di ≥ rispetto al massimo corrente. In [4, 7, 7, 1, 7] ogni 7 è un leader, ma un confronto stretto ne mantiene solo l’ultimo.
Iniziare il massimo da 0 invece che dall’ultimo elemento. [-1, -5] deve restituire entrambi, ma un massimo di 0 li esclude.
Restituire i leader nell’ordine in cui li hai trovati, [2, 6, 9, 12] invece di [12, 9, 6, 2].
Aggiungere due volte l’ultimo elemento iniziando il ciclo dall’ultimo indice dopo averlo già inserito nel risultato.
Confrontare ogni elemento solo con il suo vicino. In [5, 3, 9], 5 supera il 3 accanto a lui, ma il 9 fa sì che la risposta sia [9].

Domande frequenti3

Qual è la complessità temporale della ricerca dei leader in un array?

O(n) con un'unica scansione da destra, perché ogni elemento viene confrontato una volta con il massimo corrente. Confrontare ogni elemento con tutti quelli alla sua destra costa O(n²) nel caso peggiore, ad esempio quando tutti i valori sono uguali.

L'ultimo elemento è sempre un leader?

Sì. Un elemento leader deve essere almeno grande quanto ogni elemento alla sua destra, e l’ultimo elemento non ne ha nessuno, quindi la condizione è soddisfatta senza che ci sia nulla da controllare.

I valori uguali contano come primi?

Qui sì: un leader deve essere maggiore o uguale a ogni elemento alla sua destra, quindi in [4, 7, 7, 1, 7] tutti e tre i 7 sono leader. Alcune versioni richiedono che sia strettamente maggiore; in quel caso confronta con > e solo l’ultimo dei valori a pari merito è un leader.

def leaders(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

nums = [12, 5, 9, 3, 6, 2]

Output atteso

[12, 9, 6, 2]