C++で解く「Single Number III」：XOR演算で一度だけ現れる2つの数を見つける方法

問題の概要

整数の配列が与えられ、そのうちちょうど2つの要素だけが一度しか現れず、それ以外の要素はすべて2回現れるものとします。このとき、一度しか現れない2つの数を見つける関数を定義する必要があります。

例えば、配列 [1, 2, 3, 1, 5, 2] が与えられた場合、出力は [3, 5] となります。

解法のアプローチ：XOR（排他的論理和）を活用

この問題は、ビット演算のXORを使うことで効率的に解くことができます。同じ数同士をXORすると0に打ち消し合うという性質を利用します。具体的な手順は以下の通りです。

1. xor_res を 0 に初期化します。
2. 配列のすべての要素に対してXORを計算します。
   xor_res := xor_res XOR nums[i]（i は 0 から配列のサイズまで）
   → 2回現れる数は打ち消し合い、最終的に残るのは「一度しか現れない2つの数のXOR結果」です。
3. pos を 0 に初期化します。
4. xor_res の中で値が 1 になっているビット位置を探します。
   xor_res AND 2^pos が 0 の間、pos を 1 ずつ増やしていきます。
   → このビットは、2つの一意な数が互いに異なるビット位置を示しています。
5. num1 を 0 に初期化します。
6. pos 番目のビットが立っている要素だけをXORします。
   nums[i] AND 2^pos が 0 でない場合、num1 := num1 XOR nums[i]
   → これにより、片方の一意な数が num1 として求まります。
7. num2 を計算します。
   num2 := xor_res XOR num1
   → もう片方の一意な数が導き出されます。
8. num1 と num2 を返却します。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector <int> singleNumber(vector<int>& nums) {
        int xor_result = 0;
        for (int i=0;i < nums.size(); i++) {
            xor_result = xor_result ^ nums[i];
        }
        int pos = 0;
        while ((xor_result & (1 << pos)) == 0) {
            pos++;
        }
        int num1 = 0;
        for (int i=0;i < nums.size(); i++) {
            if ((nums[i] & (1 << pos)) != 0) {
                num1 = num1 ^ nums[i];
            }
        }
        int num2 = xor_result ^ num1;
        vector<int> result = {num1, num2};
        return result;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,1,3,2,5};
    print_vector(ob.singleNumber(v));
}

入力例

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

出力例

[3, 5]

アルゴリズムのポイントと計算量

この手法の鍵となるのは、次の2つのXORの性質です。

• 同じ数を2回XORすると0になる（a XOR a = 0）
• 任意の数と0をXORすると元の数になる（a XOR 0 = a）

まず全要素のXORを取ることで、重複する数をすべて消去し、「2つの一意な数のXOR結果」だけを残します。この結果には、2つの数が異なるビット位置が必ず1つ以上存在するため、そのビットを基準に配列を2つのグループに分ければ、それぞれのグループ内で一意な数が1つずつ孤立します。

計算量は、配列を走査する回数が定数回であるため時間計算量 O(n)、追加の変数のみを使用するため空間計算量 O(1) となり、ハッシュマップなどを使う方法よりもメモリ効率に優れた解法です。