C++で配列内の階乗の合計を検索します

ソートされた配列Aがあるとします。すべての要素が2回表示されますが、1つの要素が1回だけ存在します。その要素を見つける必要があります。配列が[1、1、3、3、4、4、5、6、6、7、7、9、9]の場合、単一の要素は5です。

これを解決するために二分探索アプローチを使用します。単一要素の前のすべての要素は、インデックス0、2、4、…で最初に出現し、インデックス1、3、5、…で最初に出現しますが、単一要素の後、最初の番号のすべての出現は奇数インデックスになり、 2番目の要素は偶数のインデックス位置にあります。

したがって、最初に中央のインデックスmidを見つけ、midが偶数の場合は、A[mid]とA[mid + 1]を比較します。両方が同じ場合は、必要に応じて左または右に移動します。それ以外の場合、中央が奇数の場合は、A[mid]とA[mid – 1]を比較します。同じ場合は、必要に応じて左または右に移動します。

例

#include<iostream>
using namespace std;
void findSingleElement(int *arr, int left, int right) {
   if (left > right)
      return;
   if (left==right) {
      cout << "The required element is: "<< arr[left];
      return;
   }
   int mid = (left + right) / 2;
   if (mid%2 == 0) {
      if (arr[mid] == arr[mid+1])
         findSingleElement(arr, mid+2, right);
      else
         findSingleElement(arr, left, mid);
   }else{
      if (arr[mid] == arr[mid-1])
         findSingleElement(arr, mid+1, right);
      else
         findSingleElement(arr, left, mid-1);
   }
}
int main() {
   int arr[] = {1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9};
   int len = sizeof(arr)/sizeof(arr[0]);
   findSingleElement(arr, 0, len-1);
}

出力

The required element is: 5