資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
