Phần tử đầu tiên xuất hiện chẵn lần trong mảng C++

Trong bài toán này, chúng ta được cho mảng arr[] gồm N số nguyên. Nhiệm vụ là tìm phần tử đầu tiên xuất hiện số lần chẵn trong mảng. Nếu không có trả về -1.

Ví dụ minh họa

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

Phương pháp giải

Sử dụng hash map lưu trữ trạng thái chẵn/lẻ (toggle) của tần suất xuất hiện. Duyệt mảng, toggle trạng thái cho mỗi phần tử. Sau đó duyệt lại mảng để tìm phần tử đầu tiên có trạng thái true (chẵn lần).

Ví dụ chương trình

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

int findFirstEvenFreqVal(int arr[], int n){
    unordered_map<int, bool> freqTogMap;
    for (int i = 0; i < n; i++){
        if (freqTogMap.find(arr[i]) == freqTogMap.end())
            freqTogMap.insert({arr[i], false});
        else {
            bool val = freqTogMap[arr[i]];
            freqTogMap[arr[i]] = !val;
        }
    }
    for (int j = 0; j < n; j++){
        if (freqTogMap[arr[j]] == true) return arr[j];
    }
    return -1;
}

int main(){
    int arr[] = {2, 4, 6, 8, 1, 6};
    cout << "Phần tử đầu tiên xuất hiện chẵn lần là " << findFirstEvenFreqVal(arr, 6);
    return 0;
}

Kết quả

Phần tử đầu tiên xuất hiện chẵn lần là 6