หา Element แรกที่ซ้ำใน Array ของ Integer ใน C++

ในปัญหานี้ เราได้รับ array arr[] ขนาด n งานคือหา element แรกที่เกิดซ้ำ (first repeating element)

ตัวอย่าง

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

4 และ 1 ซ้ำทั้งคู่ แต่ 4 ปรากฏก่อน (index 0 vs index 1)

วิธีที่ 1: Nested Loop O(N²) - ช้า

วิธีที่ 2: Hash Set + Reverse Traversal O(N) (แนะนำ)

1. Traverse จากขวาไปซ้าย
2. เก็บ element ที่เจอใน Hash Set
3. ถ้าเจอ element ที่อยู่ใน set แล้ว → อัปเดต minIndex
4. สุดท้ายคืนค่า arr[minIndex]

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int findFirstRepeating(int arr[], int n) {
    unordered_set seen;
    int minIndex = -1;
    
    for (int i = n - 1; i >= 0; i--) {
        if (seen.count(arr[i])) minIndex = i;
        else seen.insert(arr[i]);
    }
    return (minIndex != -1) ? arr[minIndex] : -1;
}

int main() {
    int arr[] = {4, 1, 6, 3, 4, 1, 5, 8};
    cout << findFirstRepeating(arr, 8); // 4
    return 0;
}

ผลลัพธ์

4