C++ 中数组中第一个出现偶数次的元素

在这个问题中，我们给定一个包含 N 个整数值的数组 arr[]。我们的任务是创建一个程序来查找数组中第一个出现偶数次的元素。如果存在满足条件的元素，则返回它，否则返回 -1 表示false。

让我们举个例子来理解这个问题，

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

解决方案

解决这个问题的一个简单方法是逐个考虑数组的每个元素，然后检查元素出现的频率是否为偶数，并返回数组中第一个出现频率为偶数的元素。解决这个问题的另一种方法是使用哈希表数据结构。为此，我们将遍历数组并创建一个哈希表，该哈希表存储元素及其出现频率作为切换，即基于其是否为偶数的 true 或 false。这将减少检查出现频率是否为 true 或 false 的开销，因为切换将显示所需的结果。对于映射，第一个值是 true（表示出现频率为偶数）的元素是我们所需的结果。

我们将遍历数组，对于数组中的每个值，即 arr[i]，我们将在映射中检查，

如果它不存在于映射中，则将其添加到映射中，并设置切换值为 'false'。如果它存在于映射中，则切换与其对应的当前值，即如果它是 'true'，则将其设为 'false'，如果它是 'false'，则将其设为 'true'。

在数组迭代之后，迭代映射并返回第一个具有切换值为 'true' 的对应值的元素。

示例

程序说明我们解决方案的工作原理

#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;
}

输出

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

更新于: 2022年2月1日

196 次查看

启动你的 职业生涯

通过完成课程获得认证

开始
广告