C++를 사용하여 크기가 n인 정렬된 배열에서 유일한 반복 요소 찾기

이 문제에서 우리는 배열에서 두 번 발생하는 하나의 값과 함께 1에서 N-1까지의 값을 포함하는 크기 N의 arr[]이 제공됩니다. 우리의 임무는 크기가 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

솔루션 작동을 설명하는 프로그램

#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