C++で、他の要素がすべて2回出現する配列から1回だけ出現する要素を見つける方法

問題の概要

配列Aがあるとします。この配列には2回出現する数値がいくつか含まれていますが、1回だけ出現する数値は1つのみです。この配列から、その唯一の要素を見つけ出す必要があります。

例えば、A = [1, 1, 5, 3, 2, 5, 2] の場合、出力は 3 になります。すべての数値が2回ずつ出現しているため、XOR（排他的論理和）を使うと重複する要素を互いに打ち消すことができます。これは「y XOR y = 0」というXORの性質を利用したテクニックです。

アルゴリズムの手順

• 変数 res = 0 を用意します

• 配列Aの各要素 e に対して、res := res XOR e を実行します

• 最後に res を返します

XORの重要な性質

• x XOR x = 0（同じ値同士のXORは0になる）

• x XOR 0 = x（0とのXORでは元の値が保たれる）

• 交換法則・結合法則が成り立つため、処理の順序は結果に影響しない

これらの性質により、同じ数値が2回出現すると互いに打ち消し合い、最終的に残るのは1回だけ出現した要素となります。

Pythonでの実装例

class Solution(object):
    def singleNumber(self, nums):
        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]))

C++での実装例

#include <iostream>
#include <vector>
using namespace std;

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int e : nums) {
        res ^= e;
    }
    return res;
}

int main() {
    vector<int> nums = {1, 1, 5, 3, 2, 5, 2};
    cout << singleNumber(nums) << endl;  // 出力: 3
    return 0;
}

入力

[1,1,5,3,2,5,2]

出力

3

計算量の分析

時間計算量：O(n) ― 配列を一度走査するだけで完了します。
空間計算量：O(1) ― 変数を1つ使うだけで追加メモリは不要です。

ハッシュマップなどを使う方法でも解けますが、XORを利用すれば余分なメモリを消費せずに効率的に解決できるのが大きなメリットです。