C++를 사용하여 배열에서 유일한 다른 요소 찾기

이 문제에서는 크기가 n인 arr[]이 제공됩니다. 우리의 임무는 f 배열의 유일한 다른 요소 .

배열에는 두 가지 다른 유형의 요소만 있습니다. 하나를 제외하고는 모든 요소가 동일합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

arr[] = {1, 1, 1, 2, 1, 1, 1, 1}

출력

2

솔루션 접근 방식

문제를 해결하기 위한 간단한 접근 방식은 배열을 탐색하고 배열의 다른 요소와 다른 요소를 찾아야 합니다. 이 접근 방식에는 O(N ² 의 시간 복잡도가 필요합니다. ).

O(N)의 문제를 해결하는 또 다른 방법은 해시 테이블을 사용하여 요소와 해당 발생 빈도를 저장하는 것입니다. 그리고 단일 발생 빈도로 값을 인쇄합니다.

예시

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

#include <iostream>
using namespace std;
int findDiffElementArray(int arr[], int n){
   if (n == 1)
      return -1;
   if (n == 2)
      return arr[0];
   if (arr[0] == arr[1] && arr[0] != arr[2])
      return arr[2];
   if (arr[0] == arr[2] && arr[0] != arr[1])
      return arr[1];
   if (arr[1] == arr[2] && arr[0] != arr[1])
      return arr[0];
   for (int i = 3; i < n; i++)
      if (arr[i] != arr[i - 1])
         return arr[i];
         return -1;
}
int main(){
   int arr[] = { 5, 5, 1, 5, 5, 5, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The different element in the array is "<<findDiffElementArray(arr, n);
   return 0;
}

출력

The different element in the array is 1