Tìm phần tử lặp đầu tiên trong một mảng số nguyên C ++

Trong bài toán này, chúng ta là một mảng gồm n giá trị nguyên. Nhiệm vụ của chúng ta là tìm phần tử lặp lại đầu tiên trong một mảng các số nguyên .

Chúng ta cần tìm giá trị số nguyên đầu tiên từ mảng đã xuất hiện nhiều lần trong mảng.

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

Input : arr[] = {4, 1, 8, 9, 7, 2, 1, 6, 4}
Output : 4

Giải thích -

Integers with more than one occurrence are 4 and 1.
4's first occurrence is smaller than 1. Hence the answer is 4

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

Một giải pháp đơn giản cho vấn đề là sử dụng các vòng lặp lồng nhau. Chúng ta sẽ sử dụng hai vòng lặp, vòng lặp bên ngoài để lặp lại từng giá trị nguyên của mảng và vòng lặp bên trong để kiểm tra xem có giá trị số nguyên khác trong mảng có cùng giá trị hay không. Nếu có, hãy trả về giá trị. Phương pháp này tốt nhưng trong trường hợp không có giải pháp, nó sẽ có độ phức tạp O (N2).

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

Một cách tiếp cận khác có thể giải quyết vấn đề tốt hơn là sử dụng băm. Chúng tôi sẽ duyệt qua mảng từ chỉ mục cuối cùng và sau đó cập nhật chỉ mục tối thiểu cho phần tử được tìm thấy tại chỉ mục được truy cập.

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<bits/stdc++.h>
using namespace std;
int findRepeatingElementArray(int arr[], int n){
   int minRetIndex = -1;
   set<int> visitedElements;
   for (int i = n - 1; i >= 0; i--){
      if (visitedElements.find(arr[i]) != visitedElements.end())
         minRetIndex = i;
      else
         visitedElements.insert(arr[i]);
   }
   if (minRetIndex != -1)
      return arr[minRetIndex];
   else
      return -1;
}
int main(){
   int arr[] = {4, 1, 6, 3, 4, 1, 5, 8};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The element with repeated occurence is "<<findRepeatingElementArray(arr, n);
}

Đầu ra

The element with repeated occurence is 4