इस समस्या में, हम n पूर्णांक मानों की एक सरणी गिरफ्तारी हैं। हमारा काम पूर्णांकों की एक सरणी में पहला दोहराए जाने वाले तत्व को ढूंढना है ।
हमें सरणी से पहला पूर्णांक मान खोजने की आवश्यकता है जो सरणी में एक से अधिक बार हुआ है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input : arr[] = {4, 1, 8, 9, 7, 2, 1, 6, 4}
Output : 4 स्पष्टीकरण -
Integers with more than one occurrence are 4 and 1. 4's first occurrence is smaller than 1. Hence the answer is 4
समाधान दृष्टिकोण
समस्या का एक आसान समाधान नेस्टेड लूप का उपयोग कर रहा है। हम दो छोरों का उपयोग करेंगे, बाहरी एक सरणी के प्रत्येक पूर्णांक मान को पुनरावृत्त करने के लिए और आंतरिक एक यह जांचने के लिए कि सरणी में समान मान के साथ कोई अन्य पूर्णांक मान मौजूद है या नहीं। यदि हाँ, तो मान लौटाएँ। यह तरीका अच्छा है लेकिन समाधान न होने की स्थिति में इसमें O(N2) जटिलता होगी।
समाधान दृष्टिकोण
एक अन्य दृष्टिकोण जो समस्या को बेहतर ढंग से हल कर सकता है वह है हैशिंग का उपयोग करना। हम पिछले इंडेक्स से ऐरे को ट्रैवर्स करेंगे और फिर इंडेक्स में मिले एलिमेंट के लिए मिनिमम इंडेक्स को अपडेट करेंगे।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#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);
} आउटपुट
The element with repeated occurence is 4