ในปัญหานี้ เราคืออาร์เรย์ arr ของค่าจำนวนเต็ม 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
