C++の2n+1整数要素の配列で単一を検索します

この問題では、（2n + 1）個の整数値で構成される配列が与えられます。これらすべての値のうち、n個の要素が配列に2回表示され、配列には1つの要素しかありません。それは一度現れます。私たちのタスクは、2n+1個の整数要素の配列から単一を見つけることです。

問題を理解するために例を見てみましょう

入力

arr[] = {1, 3, 5, 6, 5, 1, 3}

出力

5

ソリューションアプローチ

この問題の簡単な解決策は、要素にカウンターを使用することです。要素が検出された場合は、その値と発生回数を保存します。この後、発生数=1のテーブル内の要素を検索します。より効率的なソリューション XORを使用します。ここでは、配列のすべての要素のXORを実行します。このXORは、2回出現するすべての要素を0にします。また、値が存在する要素は、出現回数が1である要素のみです。

これは、XORのプロパティが-

- a^a = 0
- a^0 = a

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
int findSingleValue(int arr[], int n) {
   int element = 0;
   for (int i = 0; i < n; i++)
      element = element ^ arr[i];
   return element;
}
int main() {
   int arr[] = { 1, 3, 5, 6, 5, 1, 3 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The element of the array with single occurrence is "<<findSingleValue(arr, n);
   return 0;
}

出力

The element of the array with single occurrence is 6