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.
+12 скрытых тестов при отправке
Дополнительный вопрос
Тебе задают много вопросов вида: сколько чётных значений находится между индексом l и индексом r? Сможешь ли ты после одного прохода по nums отвечать на каждый вопрос за время O(1)?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Что остается, когда вы делите четное число на
2?Значение
xявляется чётным тогда и только тогда, когдаx % 2равно0. Обратите внимание: для отрицательного нечётного числа некоторые языки возвращают в качестве остатка-1, а не1.Начните счётчик с
0, прочитайте каждое значение один раз и прибавляйте1, когда остаток от деления на2равен0.
Решение
Цикл занимает одну строку; решения ломаются на проверке чётности. Во многих языках остаток от деления отрицательного числа отрицателен, поэтому -3 % 2 — это -1. Проверка x % 2 == 0 верна для любого знака в любом языке, а для счётчика не требуется дополнительная память.
Соберите чётные значения, затем подсчитайте их
Идея
Разделите задачу на два шага: выберите чётные значения, затем посчитайте, сколько вы выбрали. Значение x является чётным, если x % 2 == 0. В большинстве языков есть функция фильтрации, которая в одну строку формирует новый список, а его длина и будет ответом. Для [3, 8, 12, 5, 6] отфильтрованный список — [8, 12, 6], поэтому ответ — 3.
Это решение корректно и хорошо читается, но новый список требует O(n) памяти — здесь до 5000 значений — только ради того, чтобы один раз узнать его длину. Сами значения больше нигде не используются.
Алгоритм
- Создайте новый список, содержащий каждое
xизnums, для которогоx % 2 == 0. - Верните длину этого списка.
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)Считайте с помощью счётчика
Идея
Используй счётчик вместо списка. Начни с 0, проверь каждое значение один раз и прибавляй 1, если значение чётное. Каждое значение проверяется ровно один раз, поэтому подсчёт точен, а для хранения нужен только один целочисленный элемент.
При проверке нужно быть внимательным. В C, C++, Java, C#, JavaScript, Go, Rust, Swift и PHP остаток имеет знак числа, поэтому -3 % 2 равно -1, а не 1. При делении чётного числа остаток равен 0 независимо от его знака, поэтому проверка x % 2 == 0 всегда верна, тогда как проверка нечётности x % 2 == 1 пропускает все отрицательные нечётные числа. Для [-4, -3, 0, 7] остатки равны 0, -1, 0 и 1, поэтому в итоге счётчик будет равен 2.
Ноль тоже учитывается: 0 % 2 равно 0, значит, 0 — чётное число.
Алгоритм
- Установи
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никогда не считается нечётным и в итоге считается чётным. - Считать, что
0не является ни чётным, ни нечётным.0 = 2 × 0, поэтому это чётное число, и для[0]результат равен1. - Запись проверки бита в виде
x & 1 == 0. В C, C++ и JavaScript оператор==имеет более высокий приоритет, чем&, поэтому выражение означаетx & (1 == 0), что всегда равно0, и ничего не подсчитывается. Записывайте(x & 1) == 0. - Начинать цикл с индекса
1в языке с индексацией от 0, из-за чего пропускается первое значение, или с0в Lua и R, где первое значение имеет индекс1.
Частые вопросы4
Как в коде проверить, является ли число чётным?
Проверьте, равен ли нулю остаток от деления на 2: x % 2 == 0. Это работает с положительными числами, отрицательными числами и нулём во всех популярных языках. Ещё один способ — проверить младший бит с помощью (x & 1) == 0, поскольку двоичная запись чётных чисел заканчивается битом 0.
Является ли ноль чётным числом?
Да. Ноль, делённый на 2, равен 0 без остатка, поэтому он соответствует определению чётного числа. Он также находится между нечётными числами -1 и 1, именно там, где и должно находиться чётное число.
Почему выражение x % 2 == 1 не работает для отрицательных чисел?
В C, C++, Java, C#, JavaScript, Go, Rust, Swift и PHP остаток принимает знак делимого, поэтому -3 % 2 равно -1. Python, Ruby, Dart, Lua и R вместо этого возвращают 1. Проверка x % 2 != 0 на нечётность и x % 2 == 0 на чётность даёт одинаковый результат во всех этих языках.
Какова временная сложность подсчёта чётных чисел в массиве?
Один проход со счётчиком занимает время O(n) и требует O(1) дополнительной памяти. Нужно проверить каждое значение, поэтому ни один метод не может быть быстрее, чем O(n). Если сначала создать отфильтрованный список, получится тот же результат подсчёта, но потребуется O(n) дополнительной памяти.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def countEvens(nums):
# Напишите код здесьСлучай 1
Случай 2
Случай 3
Ввод
nums = [3, 8, 12, 5, 6]
Ожидается
3