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

Cho mảng arr[] n phần tử. Nhiệm vụ: tìm phần tử lặp lại đầu tiên (theo thứ tự xuất hiện trong mảng).

Ví dụ minh họa

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

4 và 1 đều lặp, nhưng 4 xuất hiện trước (chỉ số 0) nên là đáp án.

Phương pháp giải

Duyệt ngược mảng, dùng set lưu phần tử đã gặp. Phần tử đầu tiên (duyệt ngược) đã có trong set là phần tử lặp có chỉ số nhỏ nhất.

Ví dụ chương trình

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

int findRepeatingElementArray(int arr[], int n){
    int minRetIndex = -1;
    unordered_set<int> visited;
    for (int i = n - 1; i >= 0; i--) {
        if (visited.find(arr[i]) != visited.end()) minRetIndex = i;
        else visited.insert(arr[i]);
    }
    return (minRetIndex != -1) ? arr[minRetIndex] : -1;
}

int main(){
    int arr[] = {4, 1, 6, 3, 4, 1, 5, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Phần tử lặp đầu tiên: " << findRepeatingElementArray(arr, n);
    return 0;
}

Kết quả

Phần tử lặp đầu tiên: 4