C++ 在一个数组中找到两个出现奇数次的元素，而其他元素都出现偶数次

该问题包括在C++中找到一个数组中两个奇数次出现的元素，而其他元素都出现偶数次。数组是C++中用于存储相似数据类型的元素列表的数据结构。

我们将在输入中给出一个大小大于或等于2的数组。该数组将包含整数。数组中的每个整数都将出现偶数次，除了两个整数在数组中出现奇数次。在这个问题中，我们需要找出数组中那两个出现奇数次的元素并打印它们。

下面的示例将帮助您更好地理解这个问题：

输入

a[] = {2, 5, 15, 5, 9, 5, 15, 9}

输出

2  5

解释：给定的数组中，数字2出现一次，数字5出现三次，数字15和9出现两次。由于数组中出现奇数次的元素是2和5，所以这就是我们对这个问题的答案。

输入：

a[] = {10, 10, 10, 8, 3, 8, 10, 5}

输出

3 5

解释：在给定的数组中，整数10和8出现偶数次，其中10出现4次，8出现2次。而3和5只出现一次，因此，3和5是数组中的两个奇数元素。

输入

a[] = {2, 4}

输出结果

2 4

解释：在给定的数组中，只有两个不同的整数。由于它们都只出现一次，所以2和4将是我们的输出。

为了解决这个问题，我们可以在C++中找到不同的方法和函数。让我们尝试理解从暴力解法到优化解法的不同方法。

方法1（暴力解法）

使用嵌套的for循环，可以通过暴力解法来解决这个问题。我们将遍历给定数组从i=0到数组的大小，然后通过嵌套循环来查看元素a[i]是否再次在数组中出现，并计算它出现的次数。如果它出现了偶数次，就遍历剩下的元素；如果它出现了奇数次，就打印该元素。

可以通过以下步骤来实现这种方法：

创建一个函数，打印数组中所有出现奇数次的元素。
在一个for循环中从i=0到数组的大小进行迭代，以确定每个元素的出现次数。
声明一个变量cnt来计算数组中元素a[i]的出现次数。
现在在一个嵌套的for循环中从j=0到数组的大小迭代，并检查是否存在任何值小于i的j，使得a[i]=a[j]，如果是，则中断循环以避免检查已经被检查过的元素的出现次数。如果存在任何值大于或等于i的j，使得a[i]=a[j]，则增加cnt，以计算出现次数。
在遍历整个数组后，检查cnt是否是奇数或偶数。如果它是奇数，打印特定的元素，即a[i]。
这样，我们就能够打印出数组中两个出现奇数次的元素，而其他元素都出现偶数次。

示例：

// C++ code for finding  odd occurring elements
// in an array
#include <bits/stdc++.h>

using namespace std;

//function to print two odd occurring elements in the array
void odd_occurring(int a[], int N)
{
   cout<<"The odd occurring elements in an array are ";
   //iterating in a nested loop to check the occurrence of every element
    for (int i = 0; i < N; i++) { 
        int cnt = 0; //to count the occurrence
        for (int j = 0; j < N; j++) {
        if(a[i]==a[j] && j<i) //to avoid re-checking of the element
        {
         break;
        }
            if (a[i] == a[j]) { 
                cnt = cnt + 1; //if element appears in the array increase the count
            }
        }
        if ( cnt % 2 != 0) {   //if cnt is an odd number print the element
            cout << a[i]<< " "; 
        }
    }

}

int main()
{
    int a[] = { 12, 18, 7, 12, 7, 7, 18, 3, 9, 3 };
    int N = sizeof(a) / sizeof(a[0]);  //calculating size of the array

    odd_occurring(a, N); //calling the function

    return 0;
}

输出结果

The odd occurring elements in an array are 7 9

时间复杂度 ：O(N^2)，我们在嵌套的for循环中迭代。

空间复杂度 ：O(1)，因为我们没有使用任何额外的空间来解决问题。

方法2（使用map）

这可能是比上面的方法更好的方法。我们可以使用哈希映射来以有效的方式解决问题。我们将数组中的每个元素作为键存储在哈希映射中，并将其在数组中出现的次数作为值。然后遍历映射并检查每个键，即数组中的元素，如果它出现奇数次，则打印该元素。这就是使用哈希映射以更少的运行时间获取数组中两个出现奇数次的元素的方法。

哈希映射的语法：

unordered_map<data type-1, datatype-2> hashmap;

要解决哈希映射问题，请按照以下步骤进行：

创建一个使用哈希映射检查数组中所有元素出现情况并打印两个奇数次出现的元素的函数。
然后，我们将使用元素作为键，将它们的出现次数作为值初始化一个哈希映射。
一旦所有元素都已插入映射中，我们将迭代映射以检查数组中每个元素的出现次数。
我们将打印出现奇数次的元素。

该方法的C++代码：

示例

//C++ code for finding two odd occurring elements in the array using hashmap
#include <bits/stdc++.h>

using namespace std;

//function to find the elements occurring odd times in the array using map
void odd_occurring(int a[],int N){

   unordered_map<int, int> hm; //to store elements and their occurrences

   //storing values in unordered map
   for(int i=0;i<N;i++){ 
      hm[a[i]]++;
   }

   cout<<"The odd occurring elements in an array are ";

   for(auto it:hm){
      //if occurrence of any element is odd print the element i.e. key in map
      if((it.second%2) != 0){
         cout<<it.first<<" "; 
      }
   }
}

int main()
{
   int a[]={4,1,1,21,8,1,33,21,1,33,4,2};

   int N = sizeof(a)/sizeof(a[0]); //calculating size of the array

   odd_occurring(a, N); //calling the function


   return 0;
}

输出

The odd occurring elements in an array are 2 8

时间复杂度 ：O(N)，因为我们在数组中进行迭代以存储元素，并且哈希图的操作的时间复杂度在最坏情况下为O(N)。

空间复杂度 ：O(N)，因为我们创建了一个无序映射。

方法3（使用sort()函数）

在上述方法中，我们使用了额外的空间。可能存在一种O(1)空间复杂度和对第一种方法进行优化的方法。在这个方法中，我们将使用sort()函数来解决给定的问题。

sort()函数默认按升序对数组进行排序。

语法

sort(arr,arr+n);

传递的两个参数是在给定范围内对数组进行排序的位置。

在对数组进行排序之后，我们可以在数组中迭代从0到数组的大小，并计算每个元素出现的次数，然后打印出现奇数次的元素。

可以使用以下步骤应用此方法：

创建一个函数来打印出现奇数次的元素。
然后使用sort()函数对给定的数组进行排序。
在for循环中迭代从i=0到i数组大小。
创建两个变量j和cnt。j用于检查a[i]发生的索引范围，cnt用于计算出现的次数。
然后在while循环中迭代，直到a[i]=a[j]& j<N。增加j和cnt直到满足这个条件。
将j-1存储在i中，以避免对相同元素进行迭代，然后检查cnt是否为奇数，如果是，则打印出特定元素。
我们可以以这种方式打印出数组中出现奇数次的所有元素。

用于此方法的C++代码：

示例

//C++ program to find two odd occurring elements using sort function
#include <bits/stdc++.h>

using namespace std;

//function find the odd occurring elements using sort() function
void odd_occurring(int a[],int N){
   sort(a,a+N); //sorting the array

   cout<<"The odd occurring elements are ";

   for(int i=0;i<N;i++){

      int j=i; //to check number of times the element is present in the array
      int cnt=0; //to count the occurrence of each element

      while(a[i]==a[j] && j<N){  
         cnt++;  //increase the count every time 
         j++; //increase j by 1 
      }
      i=j-1;  //store the last index we checked in i

      //if cnt is an odd number print the particular element
      if(cnt%2 !=0){
         cout<<a[i]<<" ";
      }
   }
}

int main()
{
   int a[]={1,3,10,3,1,1,3,10,1,5,1,5};
    int N = sizeof(a) / sizeof(a[0]);  //calculating size of the array

    odd_occurring(a, N); //calling the function


   return 0;
}