C++でソート済み配列から一度だけ現れる要素を見つける方法

整数のみで構成されたソート済み配列を考えます。この配列では、ある1つの要素を除いて、すべての要素がちょうど2回ずつ出現します。この「一度だけ現れる要素」を見つけるのが本記事の目的です。

例えば、配列が [1, 1, 2, 3, 3, 4, 4, 8, 8] の場合、一度だけ現れる要素は 2 となるため、出力は 2 になります。

解法アプローチ:XOR(排他的論理和)を活用

この問題は、XOR の性質を利用することでシンプルに解けます。XOR には「同じ値同士を演算すると 0 になり、0 との演算では元の値が残る」という性質があります。そのため、ペアで出現する要素はすべて打ち消し合い、最後に残るのは一度だけ現れた要素です。

具体的な手順は以下の通りです。

• 変数 ans を 0 で初期化する
• 0 から配列 nums のサイズまでループを回す
• 各要素について ans に nums[i] を XOR する
• ループ終了後の ans を返す

C++での実装例

以下の実装を見ると、より理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int singleNonDuplicate(vector<int>& nums) {
      int ans = 0;
      for(int i = 0;i < nums.size(); i++)ans ^= nums[i];
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,2,3,3,4,4,8,8};
   cout << (ob.singleNonDuplicate(v));
}

入力

[1,1,2,3,3,4,4,8,8]

出力

2

計算量の改善:二分探索による O(log n) アプローチ

XOR を使った上記の方法はシンプルですが、計算量は O(n) となります。ここで注目すべきは、配列がソート済みであるという点です。この性質を利用すると、二分探索によって O(log n) まで計算量を削減できます。

ポイントは、ペアの要素は必ず偶数インデックスから始まるという規則性です。中央のインデックス mid を確認し、ペアが崩れている位置が左側か右側かを判断しながら探索範囲を半分に絞っていくことで、効率的に目的の要素を特定できます。

まとめ

一度だけ現れる要素の探索問題は、XOR の性質を使えば O(n) の時間で簡単に解けます。さらに配列がソート済みであれば、二分探索を組み合わせることで O(log n) まで高速化できるため、実務やコーディング面接においても覚えておくと役立つテクニックです。