数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究数组中两个出现奇数次的元素，其他所有元素出现偶数次
这个问题包括在 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 出现两次。而 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 增加 i 以计算出现次数。
遍历整个数组后，检查 cnt 是奇数还是偶数。如果是奇数，则打印特定元素，即 a[i]。
这样，我们就可以打印数组中两个出现奇数次的元素，其中所有其他元素出现偶数次。
该方法的 C++ 代码
示例
// 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 1，直到它满足此条件。
将 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;
}
输出
The odd occurring elements are 1 3
时间复杂度：O(N*logN)，sort() 函数的时间复杂度。
空间复杂度：O(1)，因为我们没有使用任何额外的空间。
结论
我们讨论了如何在数组中查找两个出现奇数次的元素，其中所有其他元素出现偶数次。我们学习了如何在 C++ 中使用不同的功能和数据结构从天真的方法到有效的解决方案来解决问题。
阅读完本文后，希望您对该问题的所有疑问都已解决。
236 次浏览
