Pythonでリスト内の全要素が偶数回出現しているかどうかを確認するプログラム

リスト nums に含まれるすべての要素が偶数回出現しているかどうかを判定したいケースはよくあります。本記事では、追加のメモリをほとんど使わない「定数空間(O(1))」でこの問題を解く方法を紹介します。

たとえば、入力が nums = [8, 9, 9, 8, 5, 5] の場合、8・9・5 はそれぞれ2回ずつ出現しているため、出力は True になります。

解法のアプローチ

この問題は、次の手順で解決できます。

• まず、リスト nums の長さが奇数である場合は、少なくとも1つの要素が奇数回出現することになるため、即座に False を返します。

• リスト nums をソートします。これにより、同じ値の要素が必ず隣り合うようになります。

• インデックス 1 からリストの末尾まで走査し、nums[i] と nums[i - 1] が等しい場合は、両方の要素を 0 に置き換えます(ペアとして消し込むイメージです)。

• 最後に、リスト内の全要素の合計が 0 であれば True、そうでなければ False を返します。

この方法が正しく動作するのは、ソート後のリストでは同一の値が連続して並ぶためです。隣接するペアを順番に 0 に消し込んでいき、最終的な合計が 0 になれば、すべての要素がペア(偶数回)として出現したことになります。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(nums):
    if len(nums) & 1:
        return False
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            nums[i] = nums[i - 1] = 0
    return sum(nums) == 0

nums = [8, 9, 9, 8, 5, 5]
print(solve(nums))

なお、「len(nums) & 1」はビット演算を使って奇数判定を行うテクニックです。長さが奇数のときのみ 1 になります。

入力

[8, 9, 9, 8, 5, 5]

出力

True

計算量と注意点

時間計算量はソート処理が支配的となるため O(n log n) です。一方、リストをその場で書き換えるため、カウント用の追加メモリは不要で、空間計算量は O(1) となります。

補足として、collections.Counter を使えば「各要素の出現回数がすべて偶数か」をより直感的に判定できますが、要素ごとのカウントを保持する必要があるため O(n) の追加メモリを消費します。「定数空間」という制約がある場合は、本記事のソートベースの手法が有効です。

また、この手法は要素が非負の整数であることを前提としています。負の数が含まれる場合、奇数回出現した要素の値同士が打ち消し合って合計が偶然 0 になり、誤って True と判定される可能性があるため注意してください。そのような場合は Counter を使った方法が安全です。