C++で重複した配列から失われた要素を検索します

コンセプト

1つの要素を除いて互いに重複している2つの配列に関して、つまり、配列の1つから1つの要素が欠落していることを意味します。これは、欠落している要素を特定するためのタスクです。

入力

arr1[] = {2, 5, 6, 8, 10}
arr2[] = {5, 6, 8, 10}

出力

2

2番目の配列に2がありません。

入力

arr1[] = {3, 4, 5, 6}
arr2[] = {3, 4, 5, 6, 7}

出力

7

最初の配列に7がありません。

メソッド

ここでは、配列を反復処理して要素ごとに検証し、一致しない要素が検出されたときに欠落している要素にマークを付けるという1つの簡単なソリューションを適用します。ただし、このソリューションの欠点は、アレイのサイズに対して線形の時間が必要になることです。

二分探索アプローチに基づく別の効率的なソリューションを実装できます。ステップバイステップで説明されている以下のアルゴリズムに従います-

• より大きな配列で二分探索を開始し、（低+高）/2として中程度になります
• 両方の配列の値が同じである場合、欠落している要素は右側にある必要があるため、lowをmidとしてマークすることがわかっています
• midelementsが同じでない場合は、欠落している要素が大きな配列の左側にある必要があるため、それ以外の場合はmidと同じ高さにマークします。
• 単一要素とゼロ要素配列の場合、単一要素自体が欠落要素になるため、特殊なケースを個別に処理する必要があります。

最初の要素自体が等しくない場合、その要素は欠落している要素になることが観察されています。

例

// C++ program to find missing element from same
// arrays (except one missing element)
#include <bits/stdc++.h>
using namespace std;
// Shows function to determine missing element based on binary
// search approach. arrA[] is of larger size and
// Q is size of it. arrA[] and arrB[] are assumed
// to be in same order.
int findMissingUtil(int arrA[], int arrB[], int Q){
   // Considers special case, for only element which is
   // missing in second array
   if (Q == 1)
      return arrA[0];
   // Considers special case, for first element missing
   if (arrA[0] != arrB[0])
      return arrA[0];
   // Used to initialize current corner points
   int low = 0, high = Q - 1;
   // Iterate until low < high
   while (low < high){
      int mid = (low + high) / 2;
      // It has been observed that if element at mid indices are equal
      // then go to right subarray
      if (arrA[mid] == arrB[mid])
         low = mid;
      else
         high = mid;
         // So if low, high becomes contiguous, break
      if (low == high - 1)
      break;
   }
   // Now missing element will be at high index of
   // bigger array
   return arrA[high];
}
// So this function mainly does basic error checking
// and calls findMissingUtil
void findMissing(int arrA[], int arrB[], int P, int Q){
   if (Q == P-1)
      cout << "Missing Element is "
      << findMissingUtil(arrA, arrB, P) << endl;
   else if (P == Q-1)
      cout << "Missing Element is "
      << findMissingUtil(arrB, arrA, Q) << endl;
   else
   cout << "Invalid Input";
}
// Driver Code
int main(){
   int arrA[] = {2, 5, 6, 8, 10};
   int arrB[] = {5, 6, 8, 10};
   int P = sizeof(arrA) / sizeof(int);
   int Q = sizeof(arrB) / sizeof(int);
   findMissing(arrA, arrB, P, Q);
   return 0;
}

出力

Missing Element is 2