Count Even Numbers

Q: Wie prüfst du im Code, ob eine Zahl gerade ist?

Prüfe, ob der Rest nach der Division durch 2 null ist: x % 2 == 0 . Das funktioniert für positive Zahlen, negative Zahlen und null, sogar in Sprachen, in denen -3 % 2 -1 ergibt. Du kannst auch das niedrigste Bit mit (x & 1) == 0 prüfen.

Q: Ist null eine gerade Zahl?

Ja. Null geteilt durch 2 ergibt 0 ohne Rest und erfüllt somit die Definition einer geraden Zahl. Sie liegt außerdem zwischen den ungeraden Zahlen -1 und 1 , wo eine gerade Zahl hingehört.

Q: Wie hoch ist die Zeitkomplexität beim Zählen gerader Zahlen in einem Array?

Ein Durchlauf mit einem Zähler benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz. Jeder Wert muss überprüft werden, daher ist keine Methode schneller als O(n) .

EinsteigerArrays und Strings Mathe und Simulation

+10

Gegeben ist eine nicht leere Liste von Ganzzahlen nums. Gib zurück, wie viele ihrer Werte gerade sind. Eine Zahl ist gerade, wenn bei der Division durch 2 kein Rest bleibt. Dazu gehören 0 und negative Zahlen wie -4.

Funktion

countEvens(nums: integer-array) → integer

numsinteger-array: die Liste der zu überprüfenden Ganzzahlen
Gibt zurückinteger: die Anzahl der geraden Werte in nums

Einschränkungen

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

Beispiele

Eingabe: nums = [3, 8, 12, 5, 6]
Ausgabe: 3
Erklärung: 8, 12 und 6 sind ohne Rest durch 2 teilbar; 3 und 5 sind es nicht. Die Antwort ist 3.

Eingabe: nums = [-4, -3, 0, 7]
Ausgabe: 2
Erklärung: -4 = 2 × (-2) und 0 = 2 × 0, also sind beide gerade. -3 und 7 sind ungerade, und die Anzahl beträgt 2.

Eingabe: nums = [1, 9, 15]
Ausgabe: 0
Erklärung: 1, 9 und 15 sind alle ungerade, also ist die Antwort 0.

Weiterführende Frage

Du erhältst viele Fragen: Wie viele geraden Werte liegen zwischen dem Index l und dem Index r? Kannst du nach einem Durchlauf über nums jede Frage in O(1)-Zeit beantworten?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Prüfe jeden Wert einmal und zähle diejenigen, bei denen beim Teilen durch 2 der Rest 0 ist. Den Rest mit 0 zu vergleichen, statt mit 1 auf Ungerade zu prüfen, funktioniert auch bei negativen Zahlen korrekt.

Sammle die geraden Werte und zähle sie dann.

Idee

Wähle mit einem Filter die geraden Werte aus und gib dann die Länge des Ergebnisses zurück. Für [3, 8, 12, 5, 6] lautet die gefilterte Liste [8, 12, 6], also ist die Antwort 3.

Der Zeitaufwand beträgt O(n), aber die neue Liste benötigt O(n) Speicherplatz für bis zu 5000 Werte, nur um ihre Länge einmal auszulesen.

Algorithmus

Erstelle eine neue Liste, die jedes x in nums enthält, für das x % 2 == 0 gilt.
Gib die Länge dieser Liste zurück.

def countEvens(nums):
    evens = [x for x in nums if x % 2 == 0]
    return len(evens)

Zähle mit einem laufenden Zähler

Idee

Verwende statt einer Liste einen Zähler und erhöhe ihn für jeden Wert mit x % 2 == 0 um 1. Bei einer geraden Zahl bleibt unabhängig von ihrem Vorzeichen der Rest 0, daher trifft die Bedingung in jeder Sprache auf -4 und 0 zu. Ein Test auf ungerade Zahlen mit x % 2 == 1 funktioniert dagegen nicht: In C, Java, JavaScript und den meisten C-ähnlichen Sprachen hat der Rest das Vorzeichen der Zahl, daher ist -3 % 2 gleich -1.

Ein Durchlauf und eine Ganzzahl: O(n) Zeit, O(1) Speicherplatz.

Algorithmus

Setze count auf 0.
Durchlaufe jeden Wert x in nums.
Wenn x % 2 == 0, addiere 1 zu count.
Gib nach der Schleife count zurück.

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

Stolperfallen und Grenzfälle

Die ungeraden Werte mit x % 2 == 1 zählen und von der Länge abziehen. In C-ähnlichen Sprachen ist -3 % 2 gleich -1, daher gibt [-3] statt 0 den Wert 1 zurück.
0 weder als gerade noch als ungerade behandeln. 0 = 2 × 0, daher gibt [0] den Wert 1 zurück.
Den Bit-Test als x & 1 == 0 schreiben. In C, C++ und JavaScript bindet == stärker als &, daher bedeutet es x & (1 == 0), was immer 0 ergibt und nichts zählt. Schreibe (x & 1) == 0.

Häufige Fragen3

Wie prüfst du im Code, ob eine Zahl gerade ist?

Prüfe, ob der Rest nach der Division durch 2 null ist: x % 2 == 0. Das funktioniert für positive Zahlen, negative Zahlen und null, sogar in Sprachen, in denen -3 % 2 -1 ergibt. Du kannst auch das niedrigste Bit mit (x & 1) == 0 prüfen.

Ist null eine gerade Zahl?

Ja. Null geteilt durch 2 ergibt 0 ohne Rest und erfüllt somit die Definition einer geraden Zahl. Sie liegt außerdem zwischen den ungeraden Zahlen -1 und 1, wo eine gerade Zahl hingehört.

Wie hoch ist die Zeitkomplexität beim Zählen gerader Zahlen in einem Array?

Ein Durchlauf mit einem Zähler benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz. Jeder Wert muss überprüft werden, daher ist keine Methode schneller als O(n).

def countEvens(nums):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe