題目描述 [數(shù)組中只出現(xiàn)一次的數(shù)字]
一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外甲捏，其他的數(shù)字都出現(xiàn)了兩次魁淳。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字雷袋。
解題思路一
hashmap
代碼
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
unordered_map<int, int> hashmap;
for(auto num:data)
hashmap[num]++;
vector<int> res;
for(auto it:hashmap){
if(it.second==1)
res.push_back(it.first);
}
*num1 = res[0];
*num2 = res[1];
}
};
解題思路二
轉(zhuǎn)自 https://blog.csdn.net/zh_ang_lei/article/details/50908074
首先交待一下異或的基本性質(zhì)：2個(gè)相同的數(shù)異或等于0哩罪，且異或操作(^)滿足結(jié)合律和交換律呀狼。
再來(lái)考慮一種簡(jiǎn)單一點(diǎn)的情況：一個(gè)數(shù)組中只有一個(gè)元素出現(xiàn)唯一的一次，而有其他元素都出現(xiàn)2次里烦。那么我們用0依次異或數(shù)組中每一個(gè)元素，得到的就是那個(gè)唯一的元素禁谦。因?yàn)槲覀兛梢岳媒粨Q律和結(jié)合律將相同的元素移動(dòng)到一起胁黑，那么在利用結(jié)合律，相同的元素兩兩先異或州泊，得到0丧蘸，最后得到很多0和唯一的元素異或，所以最終的答案就是那個(gè)唯一的元素遥皂。
所以力喷，如果我們能把原來(lái)問題中的數(shù)組，分成2個(gè)子數(shù)組演训，使得每個(gè)子數(shù)組中都只有一個(gè)唯一的元素以及很多成對(duì)的元素弟孟，那么我們就可以求出每個(gè)子數(shù)組中唯一的元素，最終就可以得到原數(shù)組中2個(gè)出現(xiàn)次數(shù)唯一的元素样悟。
方法是這樣的：
首先數(shù)組中所有元素依次異或拂募，因?yàn)橄嗤脑禺惢虻玫?庭猩，所以最終的答案就等于那2個(gè)唯一的元素a^b的值。
因?yàn)閍,b不同陈症，所以異或得到的答案肯定是不等于0的蔼水，那么我們就找到a^b的二進(jìn)制表示中第一個(gè)為1的位，假如是第k位录肯。而a,b兩個(gè)數(shù)在第k位上是不同的趴腋，一個(gè)為0，一個(gè)為1
接下來(lái)我們將第k位是1的分成一組论咏，第k位是0的分成一組优炬，如果2個(gè)元素相同，那么他們第k位肯定是一樣的潘靖，所以肯定被分到同一組中穿剖。而a,b則被分到2組中去了。
然后我們就可以在每個(gè)分組中異或每一個(gè)元素卦溢，最終就可以得到那2個(gè)唯一的元素糊余。
代碼
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int num = data.size();
int ret = 0;
for(int i=0; i<num; i++)
ret ^= data[i];
//找到第一個(gè)k位
int pos = 1;
while(((ret>>pos) & 1) != 1 )
pos++;
//將包含num1 and num2 分開
for(int i=0; i<num; i++)
{
if(((data[i]>>pos) & 1) != 1 )
*num1 ^= data[i];
else
*num2 ^= data[i];
}
}
};
