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

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm N giá trị nguyên. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm phần tử đầu tiên xuất hiện với số lần chẵn trong một mảng . Nếu tồn tại bất kỳ phần tử nào đáp ứng điều kiện, trả về nó, ngược lại trả về -1 biểu thị false .

Hãy lấy một ví dụ để hiểu vấn đề,

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

Phương pháp tiếp cận giải pháp

Một phương pháp đơn giản để giải quyết vấn đề là xem xét từng phần tử của mảng một rồi kiểm tra tần suất xuất hiện của phần tử đó là chẵn và trả về phần tử đầu tiên trong mảng có tần suất xuất hiện chẵn. Một phương pháp khác để giải quyết vấn đề là sử dụng bản đồ băm cấu trúc dữ liệu. Đối với điều này, chúng tôi sẽ duyệt qua mảng và tạo một bản đồ băm lưu trữ các phần tử cùng với tần suất xuất hiện của chúng dưới dạng chuyển đổi, tức là đúng hoặc sai dựa trên thực tế là nó có chẵn hay không. Điều này sẽ giảm chi phí kiểm tra tần suất xuất hiện là đúng hay sai vì nút chuyển đổi sẽ hiển thị kết quả cần thiết. Đối với bản đồ, phần tử đầu tiên có giá trị là true (biểu thị tần suất xuất hiện chẵn) là kết quả bắt buộc của chúng tôi.

Chúng tôi sẽ duyệt qua mảng và đối với mỗi giá trị, trong mảng, tức là arr [i], chúng tôi sẽ kiểm tra trong bản đồ,

Nếu nó không có trong bản đồ, hãy thêm nó vào bản đồ với giá trị chuyển đổi ' false '. Nếu nó có trong bản đồ, hãy chuyển đổi giá trị hiện tại tương ứng với nó, tức là nếu nó là ' true 'make it' false 'và nếu nó là' false 'make it' true '.

Sau khi lặp lại mảng, hãy lặp lại bản đồ và trả về giá trị đầu tiên với giá trị chuyển đổi tương ứng là ' true '.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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(pair <int,bool> (arr[i],false));
      else
      {
         bool val = freqTogMap.find(arr[i])->second;
         if (val == true)
            freqTogMap.find(arr[i])->second = false;
         else
            freqTogMap.find(arr[i])->second = true;
      }
   }
   int j = 0;
   for (j = 0; j < n; j++){
      if (freqTogMap.find(arr[j])->second == true)
         return arr[j];;
   }
   return -1;
}
int main(){
   int arr[] = { 2, 4, 6, 8, 1, 6 };
   cout<<"The first element of the array which appears even number of times is "  <<findFirstEvenFreqVal(arr, 6);
   return 0;
}

Đầu ra

The first element of the array which appears even number of times is 6