C++で1つのソートされた配列に存在する余分な要素のインデックスを検索します

この問題では、サイズnとn + 1の2つのソートされた配列arr1とarr2が与えられ、余分な要素を除いてすべての要素が同じです。私たちのタスクは、1つの並べ替えられた配列に存在する追加の要素のインデックスを見つけることです。 。

問題の説明： サイズnの配列に存在しないn+1サイズの配列から要素のインデックスを見つける必要があります。

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

入力： arr1 [n] ={3、5、7、8、9、12}
arr2 [n + 1] ={3、4、5、7、8、9、12}

出力： 1

説明：

値4の要素は、インデックス1にある余分な要素です。

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

この問題の簡単な解決策は、両方の配列がソートされているという事実を使用することです。また、等しくない要素が1つしかない場合は、線形検索を実行して、arr1[]に存在しないarr2の要素を見つけることができます。

アルゴリズム：

ステップ1： iのループ->0からn+1、

ステップ1.1： 奇数の要素を見つけます。arr1[i]！=arr2 [i]の場合、ループを中断します。

ステップ2： iの値を返します。

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

例

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {
   
   int i;
   for (i = 0; i < n; i++)
      if (arr1[i] != arr2[i])
         break;
   return i;
}

int main()
{
   int arr1[] = {3, 5, 7, 8, 9, 12};
   int arr2[] = {3, 4, 5, 7, 8, 9, 12};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int extraIndex = findExtraElement(arr1, arr2, n);
   cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
   return 0;
}

出力

The extra element is at index (1) and the value is 4

このソリューションは、二分探索というより効果的な検索手法を使用することで改善できます。 線形ではなく、アルゴリズムの計算時間を短縮します。

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

例

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {
   
   int extraIndex = n;
   int start = 0, end = n - 1;
   while (start <= end)
   {
      int mid = (start + end) / 2;
      if (arr2[mid] == arr1[mid])
         start = mid + 1;
      else
      {
         extraIndex = mid;
         end = mid - 1;
      }
   }
   return extraIndex;
}

int main()
{
   int arr1[] = {3, 5, 7, 8, 9, 12};
   int arr2[] = {3, 4, 5, 7, 8, 9, 12};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int extraIndex = findExtraElement(arr1, arr2, n);
   cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
   return 0;
}

出力

The extra element is at index (1) and the value is 4

別のアプローチ：

この問題を解決するもう1つのアプローチは、余分な要素である2つの配列間の絶対差を見つけることです。次に、サイズn+1の配列でこの余分な要素のインデックスを見つける必要があります。これは、検索アルゴリズムを使用して実行できます。

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

例

#include <iostream>
using namespace std;

int calcArraysum(int arr[], int n){
   int sum = 0;
   for(int i = 0; i < n; i++)
      sum += arr[i];
   return sum;
}

int findExtraElement(int arr1[], int arr2[], int n) {
   
   int extraValue = calcArraysum(arr2, n+1) - calcArraysum(arr1, n);

   for (int i = 0; i < n; i++)
   {
      if (arr2[i] == extraValue)
         return i;
   }
   return -1;
}

int main()
{
   int arr1[] = {3, 5, 7, 8, 9, 12};
   int arr2[] = {3, 4, 5, 7, 8, 9, 12};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int extraIndex = findExtraElement(arr1, arr2, n);
   cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
   return 0;
}

出力

The extra element is at index (1) and the value is 4