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 を1回走査した後、各質問に O(1) 時間で答えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
偶数を
2で割ったとき、余りはいくつですか？値
xが偶数であるのは、x % 2がちょうど0の場合です。注意してください。負の奇数の場合、言語によっては余りが1ではなく-1になります。カウンターを
0で開始し、各値を1回ずつ読み取り、2で割った余りが0の場合は1を加えます。
解説
ループは1行で済みます。解法がつまずくのは偶数かどうかの判定です。多くの言語では、負の数の剰余は負になるため、-3 % 2 は -1 です。x % 2 == 0 を判定すれば、どの言語でも符号にかかわらず正しく、カウンターを増やしていくだけなら追加のメモリも必要ありません。
偶数の値を集めてから、その数を数えます
考え方
この課題を2つの手順に分けます。偶数の値を選び出し、次に選んだ値の個数を数えます。値 x は、x % 2 == 0 のとき偶数です。ほとんどの言語には、新しいリストを1行で作成するフィルター関数があり、その長さが答えになります。[3, 8, 12, 5, 6] の場合、フィルター後のリストは [8, 12, 6] なので、答えは 3 です。
これは正しく、読みやすい方法ですが、新しいリストには O(n) のメモリが必要です。ここでは最大 5000 個の値を保持しますが、その長さを一度読むためだけです。値そのものはその後使われません。
アルゴリズム
numsの中でx % 2 == 0を満たすすべてのxを含む新しいリストを作成します。- そのリストの長さを返します。
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)カウンターを増やしながら数える
考え方
リストの代わりにカウンターを使います。0から始め、各値を一度ずつ確認し、値が偶数なら1を加えます。すべての値を正確に一度ずつ確認するため、数えた結果は正確で、必要なメモリは整数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に設定します。nums内のすべての値xを順に処理します。x % 2 == 0の場合、countに1を加えます。- ループの後、
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は偶数であり、[0]は1を返します。- ビット判定を
x & 1 == 0と書いています。C、C++、JavaScriptでは、==は&より優先順位が高いため、これはx & (1 == 0)を意味し、常に0となって何も数えません。(x & 1) == 0と書いてください。 - 0始まりの言語でループをインデックス
1から始めると最初の値を飛ばしてしまいます。一方、LuaやRでは最初の値のインデックスは1なので、0から始めてしまうと同様の問題が起きます。
よくある質問4
コードで数値が偶数かどうかを確認するにはどうすればよいですか？
2で割った余りがゼロかどうかを確認します：x % 2 == 0。これは、主要なすべての言語で正の数、負の数、ゼロに対して機能します。別の方法として、偶数は末尾のビットが0になるため、最下位ビットを(x & 1) == 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 は、どの言語でも同じ結果になります。
配列内の偶数を数える時間計算量はどれくらいですか？
カウンターを使った1回の走査には、時間 O(n)、追加の空間 O(1) が必要です。すべての値を確認する必要があるため、O(n) より速い方法はありません。先にフィルター済みのリストを作成しても同じ個数が得られますが、追加で O(n) のメモリを使用します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def countEvens(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [3, 8, 12, 5, 6]
期待値
3