Count Even Numbers
Дан непустой список целых чисел nums. Верните количество чётных значений в нём. Число является чётным, если при делении на 2 не остаётся остатка; к таким числам относятся 0 и отрицательные числа, например -4.
Функция
- numsinteger-array
- список целых чисел для проверки
- Возвращаетinteger
- количество чётных значений в nums
Ограничения
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Примеры
- Ввод
- nums = [3, 8, 12, 5, 6]
- Вывод
- 3
- Пояснение
8,12и6делятся на2без остатка;3и5— нет. Ответ:3.
- Ввод
- nums = [-4, -3, 0, 7]
- Вывод
- 2
- Пояснение
-4 = 2 × (-2)и0 = 2 × 0, поэтому оба числа чётные.-3и7— нечётные, а их количество равно2.
- Ввод
- nums = [1, 9, 15]
- Вывод
- 0
- Пояснение
1,9и15— все нечётные, поэтому ответ —0.
Дополнительный вопрос
Тебе часто задают вопрос: сколько чётных значений находится между индексом l и индексом r? Можно ли после одного прохода по nums отвечать на каждый такой вопрос за время O(1)?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Что остаётся, когда вы делите чётное число на
2?Значение
xявляется чётным тогда и только тогда, когдаx % 2равно0. Обрати внимание: для отрицательного нечётного числа некоторые языки возвращают в качестве остатка-1, а не1.Начни счётчик с
0, прочитай каждое значение один раз и добавляй1, когда остаток от деления на2равен0.
Решение
Проверьте каждое значение один раз и посчитайте те, которые при делении на 2 дают остаток 0. Сравнение остатка с 0, а не проверка на нечётность с помощью 1, корректно работает и для отрицательных чисел.
Соберите чётные значения, затем посчитайте их
Идея
Отберите чётные значения с помощью фильтра, затем верните длину результата. Для [3, 8, 12, 5, 6] отфильтрованный список — [8, 12, 6], поэтому ответ — 3.
Время работы — O(n), но новый список требует O(n) памяти для хранения до 5000 значений, чтобы затем лишь один раз прочитать его длину.
Алгоритм
- Создай новый список, содержащий все
xизnums, для которыхx % 2 == 0. - Верни длину этого списка.
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)Считайте с помощью счётчика
Идея
Используй счётчик вместо списка и прибавляй 1 для каждого значения, для которого выполняется x % 2 == 0. При делении чётного числа остаток равен 0 независимо от знака, поэтому проверка работает для -4 и 0 в любом языке. Проверка на нечётность в виде x % 2 == 1 не работает: в C, Java, JavaScript и большинстве языков, похожих на C, знак остатка совпадает со знаком числа, поэтому -3 % 2 равно -1.
Один проход и одно целое число: время — O(n), память — O(1).
Алгоритм
- Установи
countв значение0. - Перебери каждое значение
xвnums. - Если
x % 2 == 0, прибавь1кcount. - После цикла верни
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
Ловушки и крайние случаи
- Подсчёт нечётных значений с помощью
x % 2 == 1и вычитание их количества из длины. В языках семейства C-3 % 2равно-1, поэтому[-3]возвращает 1 вместо 0. - Считать, что
0не является ни чётным, ни нечётным.0 = 2 × 0, поэтому[0]возвращает1. - Запись проверки бита в виде
x & 1 == 0. В C, C++ и JavaScript оператор==имеет более высокий приоритет, чем&, поэтому выражение означаетx & (1 == 0), результат которого всегда равен0, и ничего не подсчитывается. Запиши(x & 1) == 0.
Частые вопросы3
Как проверить в коде, является ли число чётным?
Проверьте, равен ли нулю остаток после деления на 2: x % 2 == 0. Это работает для положительных и отрицательных чисел, а также для нуля, даже в языках, где -3 % 2 равно -1. Также можно проверить младший бит с помощью (x & 1) == 0.
Является ли ноль чётным числом?
Да. Ноль, разделённый на 2, равен 0 без остатка, поэтому он соответствует определению чётного числа. Он также находится между нечётными числами -1 и 1, где и должно быть чётное число.
Какова временная сложность подсчёта чётных чисел в массиве?
Один проход со счётчиком занимает время O(n) и требует O(1) дополнительной памяти. Нужно проверить каждое значение, поэтому ни один метод не работает быстрее, чем за O(n).
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def countEvens(nums):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргумент
nums = [3, 8, 12, 5, 6]
Ожидаемый вывод
3