Pythonで一度だけ現れる数値を見つける方法(XOR演算の活用)

配列Aの中に、2回ずつ出現する数値がたくさん含まれているとします。その中で、たった1つだけ1回しか出現しない要素があります。この要素を配列から見つけ出すのが課題です。

例えば、A = [1, 1, 5, 3, 2, 5, 2] の場合、出力は 3 になります。すべての数値が2回ずつ現れるため、XOR(排他的論理和)を使うことで、ペアになる要素を打ち消し合って残りの一意な要素を導き出せます。これは、同じ数値同士のXORが必ず0になるという性質(y XOR y = 0)を利用したテクニックです。

さらに、XORには交換法則と結合法則が成り立つため、要素の出現順序に関係なく、同じ数値同士は必ずペアとして打ち消されます。結果として、計算の最後に残るのは「一度だけ出現した数値」だけになります。

解法の手順

• 変数 res を 0 で初期化します
• 配列 A の各要素 e に対して、res = res XOR e を実行します
• 最終的な res の値を返します

実装例

以下のコードで、実際の動作を確認してみましょう。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = nums[0]
        for i in range(1, len(nums)):
            ans ^= nums[i]
        return ans

ob1 = Solution()
print(ob1.singleNumber([1, 1, 5, 3, 2, 5, 2]))

入力

nums = [1,1,5,3,2,5,2]

出力

3

計算の流れ

この例では、次のようにXORが進行していきます。

• 1 XOR 1 = 0(打ち消される)
• 0 XOR 5 = 5
• 5 XOR 3 = 6
• 6 XOR 2 = 4
• 4 XOR 5 = 1
• 1 XOR 2 = 3

最終的に 3 が返され、これが唯一1回しか出現していない要素です。

このアプローチのメリット

• 時間計算量: O(n) — 配列を一度だけ走査すればよいため高速です
• 空間計算量: O(1) — 追加の辞書やセットを使わないため、メモリ効率に優れています

ハッシュマップなどで出現回数をカウントする方法もありますが、追加メモリが必要になるため、XORを利用したこの方法が最もシンプルかつ効率的です。