Count Even Numbers
Ti viene fornita una lista non vuota di numeri interi nums. Restituisci quanti dei suoi valori sono pari. Un numero è pari quando dividendolo per 2 non rimane alcun resto; questo include 0 e i numeri negativi come -4.
Funzione
- numsinteger-array
- l'elenco di numeri interi da controllare
- Restituisceinteger
- il numero di valori pari in nums
Vincoli
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Esempi
- Input
- nums = [3, 8, 12, 5, 6]
- Output
- 3
- Spiegazione
8,12e6sono divisibili per2senza resto, mentre3e5lasciano un resto. Questo rende3valori pari.
- Input
- nums = [-4, -3, 0, 7]
- Output
- 2
- Spiegazione
-4 = 2 × (-2)e0 = 2 × 0, quindi entrambi sono pari.-3e7sono dispari, e il conteggio è2.
- Input
- nums = [1, 9, 15]
- Output
- 0
- Spiegazione
1,9e15sono tutti dispari, quindi nessun valore viene conteggiato e la risposta è0.
+12 test nascosti all’invio
Per approfondire
Ricevi molte domande del tipo: quanti valori pari si trovano tra l’indice l e l’indice r? Dopo un’unica iterazione su nums, puoi rispondere a ciascuna domanda in tempo O(1)?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Quanto resta quando dividi un numero pari per
2?Un valore
xè pari esattamente quandox % 2è0. Attenzione: per un numero dispari negativo, alcuni linguaggi restituiscono-1come resto, non1.Avvia un contatore da
0, leggi ogni valore una volta e aggiungi1ogni volta che il resto della divisione per2è0.
Soluzione
Il ciclo è una riga; è il test di parità il punto in cui le soluzioni si inceppano. In molti linguaggi, il resto di un numero negativo è negativo, quindi -3 % 2 è -1. Verificare x % 2 == 0 è corretto per entrambi i segni in qualsiasi linguaggio, e un contatore incrementale non richiede memoria aggiuntiva.
Raccogli i valori pari, poi contali
Intuizione
Dividi il compito in due passaggi: individua i valori pari, poi conta quelli che hai selezionato. Un valore x è pari quando x % 2 == 0. La maggior parte dei linguaggi ha una funzione di filtro che crea la nuova lista in una sola riga, e la sua lunghezza è la risposta. Per [3, 8, 12, 5, 6] la lista filtrata è [8, 12, 6], quindi la risposta è 3.
È corretto e si legge bene, ma la nuova lista richiede memoria O(n), fino a 5000 valori in questo caso, solo per leggerne una volta la lunghezza. I valori in sé non vengono mai più usati.
Algoritmo
- Crea una nuova lista contenente ogni
xinnumsper cuix % 2 == 0. - Restituisci la lunghezza di quella lista.
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)Conta con un contatore progressivo
Intuizione
Tieni un contatore invece di una lista. Inizializzalo a 0, esamina ogni valore una sola volta e aggiungi 1 quando il valore è pari. Ogni valore viene controllato esattamente una volta, quindi il conteggio è preciso e l'unica memoria necessaria è quella di un intero.
Il test richiede attenzione. In C, C++, Java, C#, JavaScript, Go, Rust, Swift e PHP il resto ha il segno del numero, quindi -3 % 2 è -1, non 1. Un numero pari ha resto 0 qualunque sia il suo segno, quindi x % 2 == 0 è sempre corretto, mentre un test per i dispari scritto come x % 2 == 1 non rileva nessun numero dispari negativo. Per [-4, -3, 0, 7] i resti sono 0, -1, 0 e 1, quindi il contatore termina a 2.
Anche lo zero viene conteggiato: 0 % 2 è 0, quindi 0 è pari.
Algoritmo
- Imposta
countsu0. - Esegui un ciclo su ogni valore
xinnums. - Se
x % 2 == 0, aggiungi1acount. - Dopo il ciclo, restituisci
count.
def countEvens(nums):
count = 0
for x in nums:
if x % 2 == 0: # 0 also works for negatives, where the remainder can be -1
count += 1
return count
Trappole e casi limite
Gli errori qui derivano dai numeri negativi e dallo zero.
- Contare i valori dispari con
x % 2 == 1e sottrarli dalla lunghezza. Nei linguaggi simili al C,-3 % 2è-1, quindi-3non viene mai contato come dispari e finisce per essere contato come pari. - Considerare
0né pari né dispari.0 = 2 × 0, quindi è pari e[0]restituisce1. - Scrivere il test dei bit come
x & 1 == 0. In C, C++ e JavaScript,==ha precedenza maggiore di&, quindi significax & (1 == 0), che è sempre0e non conta nulla. Scrivi(x & 1) == 0. - Iniziare il ciclo dall'indice
1in un linguaggio con indicizzazione a partire da 0, saltando così il primo valore, oppure da0in Lua e R, dove il primo valore si trova all'indice1.
Domande frequenti4
Come si verifica se un numero è pari nel codice?
Verifica se il resto dopo la divisione per 2 è zero: x % 2 == 0. Funziona con numeri positivi, numeri negativi e zero in tutti i linguaggi più diffusi. Un altro modo è controllare il bit meno significativo con (x & 1) == 0, perché i numeri pari terminano con un bit 0.
Zero è un numero pari?
Sì. Zero diviso per 2 è 0 senza resto, quindi rientra nella definizione di numero pari. Si trova anche tra i numeri dispari -1 e 1, proprio dove dovrebbe trovarsi un numero pari.
Perché x % 2 == 1 non funziona con i numeri negativi?
In C, C++, Java, C#, JavaScript, Go, Rust, Swift e PHP, il resto assume il segno del numero che viene diviso, quindi -3 % 2 è -1. Python, Ruby, Dart, Lua e R restituiscono invece 1. Verificare x % 2 != 0 per i numeri dispari e x % 2 == 0 per quelli pari dà la stessa risposta in tutti questi linguaggi.
Qual è la complessità temporale del conteggio dei numeri pari in un array?
Un passaggio con un contatore richiede un tempo O(n) e uno spazio aggiuntivo O(1). È necessario controllare ogni valore, quindi nessun metodo è più veloce di O(n). Creare prima un elenco filtrato restituisce lo stesso conteggio, ma usa O(n) di memoria aggiuntiva.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def countEvens(nums):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
nums = [3, 8, 12, 5, 6]
Atteso
3