C ++を使用して、サイズnのソートされた配列内の唯一の繰り返し要素を検索します

この問題では、1からN-1までの値を含むサイズNのarr []が与えられ、1つの値が配列内で2回発生します。私たちのタスクは、サイズnのソートされた配列内の唯一の繰り返し要素を見つけることです 。

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

入力

arr[] = {1, 2, 3, 4, 5, 5, 6, 7}

出力

5

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

この問題を解決する簡単な方法は、線形探索を使用して、arr[i]とarr[i+1]の値が同じかどうかを確認することです。この場合、繰り返される値であるarr[i]を返します。

例1

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

#include <iostream>
using namespace std;
int findRepeatingValueArr(int arr[], int N){
   for(int i = 0; i < N; i++){
      if(arr[i] == arr[i+1])
         return (arr[i]);
   }
   return -1;
}
int main(){
   int arr[] = {1, 2, 3, 4, 4, 5, 6};
   int N = sizeof(arr)/sizeof(arr[0]);
   cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, N);
   return 0;
}

出力

The repeating value in the array is 4

この問題を解決する別のアプローチは、バイナリ検索アルゴリズムを使用して、中間インデックスで2回発生した要素を見つけることです。中央のインデックス値が繰り返される場合は、それを出力します。インデックス位置にない場合は、右のサブアレイをトラバースします。そうでない場合は、左のサブアレイをトラバースします。

例2

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

#include <bits/stdc++.h>
using namespace std;
int findRepeatingValueArr(int arr[], int s, int e){
   if (s > e)
      return -1;
   int mid = (s + e) / 2;
   if (arr[mid] != mid + 1){
      if (mid > 0 && arr[mid]==arr[mid-1])
         return arr[mid];
         return arr[findRepeatingValueArr(arr, s, mid-1)];
   }
   return arr[findRepeatingValueArr(arr, mid+1, e)];
}
int main(){
   int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 9};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, 0, n-1);;
   return 0;
}

出力

The repeating value in the array is 6