Tìm phần tử khác nhau duy nhất trong một mảng bằng C ++

Trong bài toán này, chúng ta được cung cấp một arr [] có kích thước n. Nhiệm vụ của chúng tôi là f ind phần tử khác nhau duy nhất trong một mảng .

Chỉ có hai loại phần tử khác nhau trong mảng. Tất cả các yếu tố đều giống nhau, ngoại trừ một yếu tố.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

2

Phương pháp tiếp cận giải pháp

Một cách tiếp cận đơn giản để giải quyết vấn đề, chúng ta cần xem qua mảng và tìm các phần tử khác với các phần tử khác của mảng. Cách tiếp cận này cần độ phức tạp về thời gian là O (N ² ).

Một cách tiếp cận khác để giải quyết vấn đề trong O (N) là sử dụng bảng băm để lưu trữ các phần tử và tần suất xuất hiện của chúng. Và in giá trị với một tần suất xuất hiện duy nhất.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

The different element in the array is 1