配列内で奇数回出現する数値を見つけるC/C++プログラム

正の整数からなる配列の中で、奇数回出現する数値を見つけるC++プログラムを紹介します。この配列では、答えとなる1つの数だけが奇数回出現し、それ以外のすべての数値は偶数回出現するものとします。

入力: arr[] = {5, 7, 8, 8, 5, 8, 8, 7, 7}
出力: 7

アルゴリズムの解説

この方法では、二重ループを使用します。外側のループで配列の各要素を1つずつ順番に走査し、内側のループでその要素が配列全体に出現する回数をカウントします。カウントした結果が奇数であれば、その要素が求める答えとなります。

上記の例では、数値「5」は2回、「8」は4回出現していますが、「7」だけが3回出現しているため、出力は「7」になります。

なお、この二重ループによる手法の計算量はO(n²)です。より効率的に処理したい場合は、XOR（排他的論理和）を活用する方法があります。同じ数同士のXORは0になるという性質を利用すると、O(n)の計算量で奇数回出現する数値を特定できます。

実装例

#include <iostream>
using namespace std;
int Odd(int arr[], int n){
   for (int i = 0; i < n; i++) {
      int ctr = 0;
      for (int j = 0; j < n; j++) {
         if (arr[i] == arr[j])
            ctr++;
      }
      if (ctr % 2 != 0)
         return arr[i];
   }
   return -1;
}
int main() {
   int arr[] = {5, 7, 8, 8, 5, 8, 8, 7, 7};
   int n = 9;
   cout <<Odd(arr, n);
   return 0;
}

このプログラムを実行すると、配列内で奇数回出現している「7」が出力されます。該当する数値が存在しない場合には、関数は-1を返すようになっています。