Count Even Numbers

Q: Come si verifica nel codice se un numero è pari?

Verifica se il resto dopo la divisione per 2 è zero: x % 2 == 0 . Funziona con numeri positivi, numeri negativi e zero, anche nei linguaggi in cui -3 % 2 è -1 . Puoi anche controllare il bit meno significativo con (x & 1) == 0 .

Q: Zero è un numero pari?

Sì. Zero diviso per 2 è 0 senza resto, quindi soddisfa la definizione di numero pari. Si trova anche tra i numeri dispari -1 e 1 , dove si colloca un numero pari.

Q: Qual è la complessità temporale del conteggio dei numeri pari in un array?

Una passata con un contatore richiede un tempo O(n) e uno spazio aggiuntivo O(1) . Ogni valore deve essere controllato, quindi nessun metodo è più veloce di O(n) .

PrincipianteArray e stringhe Matematica e simulazione

+10

Data una lista non vuota di numeri interi nums, restituisci quanti dei suoi valori sono pari. Un numero è pari quando, dividendolo per 2, non resta alcun resto; questo include 0 e i numeri negativi come -4.

Funzione

countEvens(nums: integer-array) → integer

numsinteger-array: la lista di numeri interi da controllare
Restituisceinteger: il numero di valori pari in nums

Vincoli

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

Esempi

Input: nums = [3, 8, 12, 5, 6]
Output: 3
Spiegazione: 8, 12 e 6 sono divisibili per 2 senza resto; 3 e 5 no. La risposta è 3.

Input: nums = [-4, -3, 0, 7]
Output: 2
Spiegazione: -4 = 2 × (-2) e 0 = 2 × 0, quindi entrambi sono pari. -3 e 7 sono dispari, e il conteggio è 2.

Input: nums = [1, 9, 15]
Output: 0
Spiegazione: 1, 9 e 15 sono tutti dispari, quindi la risposta è 0.

Per approfondire

Ricevi molte domande: quanti valori pari si trovano tra l’indice l e l’indice r? Dopo un’unica scansione di nums, riesci a rispondere a ciascuna in tempo O(1)?

Suggerimenti

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

0 di 3 aperti

Soluzione

Controlla ogni valore una volta e conta quelli che hanno resto 0 quando vengono divisi per 2. Confrontare il resto con 0, invece di verificare se un numero è dispari controllando se è 1, gestisce correttamente i numeri negativi.

Raccogli i valori pari, poi contali

Intuizione

Seleziona i valori pari con un filtro, poi restituisci la lunghezza del risultato. Per [3, 8, 12, 5, 6] la lista filtrata è [8, 12, 6], quindi la risposta è 3.

Il tempo è O(n), ma la nuova lista richiede O(n) di memoria, fino a 5000 valori, solo per leggerne la lunghezza una volta.

Algoritmo

Crea una nuova lista contenente ogni x in nums per cui x % 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 e aggiungi 1 per ogni valore con x % 2 == 0. Un numero pari ha resto 0 qualunque sia il suo segno, quindi il test è valido per -4 e 0 in ogni linguaggio. Un test per i numeri dispari scritto x % 2 == 1 non lo è: in C, Java, JavaScript e nella maggior parte dei linguaggi simili a C, il resto ha il segno del numero, quindi -3 % 2 è -1.

Un'unica scansione e un intero: tempo O(n), spazio O(1).

Algoritmo

Imposta count su 0.
Itera su ogni valore x in nums.
Se x % 2 == 0, aggiungi 1 a count.
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

Contare i valori dispari con x % 2 == 1 e sottrarli dalla lunghezza. Nei linguaggi simili al C, -3 % 2 è -1, quindi [-3] restituisce 1 invece di 0.
Considerare 0 né pari né dispari. 0 = 2 × 0, quindi [0] restituisce 1.
Scrivere il test bit a bit come x & 1 == 0. In C, C++ e JavaScript, == ha precedenza maggiore di &, quindi significa x & (1 == 0), che è sempre 0 e non conta nulla. Scrivi (x & 1) == 0.

Domande frequenti3

Come si verifica nel codice se un numero è pari?

Verifica se il resto dopo la divisione per 2 è zero: x % 2 == 0. Funziona con numeri positivi, numeri negativi e zero, anche nei linguaggi in cui -3 % 2 è -1. Puoi anche controllare il bit meno significativo con (x & 1) == 0.

Zero è un numero pari?

Sì. Zero diviso per 2 è 0 senza resto, quindi soddisfa la definizione di numero pari. Si trova anche tra i numeri dispari -1 e 1, dove si colloca un numero pari.

Qual è la complessità temporale del conteggio dei numeri pari in un array?

Una passata con un contatore richiede un tempo O(n) e uno spazio aggiuntivo O(1). Ogni valore deve essere controllato, quindi nessun metodo è più veloce di O(n).

def countEvens(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

nums = [3, 8, 12, 5, 6]

Output atteso