数组中只出现一次的两个数字
数组中只出现一次的两个数字
http://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8
- 前置:一串数异或,若只有一个只出现一次,其他两两相同,则结果是它本身
- 因此,若有两个数出现一次,所有数异或的结果是
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> FindNumsAppearOnce(vector<int>& array) {
// 位运算 哈希
// 很容易想到On的大哈希表 但是要求时间复杂度O1
// 把所有数进行异或,剩下的就是不一样的
// 但现在我们有两个数
int tmp = 0;
for (int i : array) {
tmp = tmp^i;
} // tmp = a xor b
int mask = 1; // 00000001
while((tmp & mask) == 0){
mask <<= 1; // 0..010..0
}
int a = 0, b = 0;
for(int num : array){
if((num & mask) == 0){
a ^= num;
}else{
b ^= num;
}
}
if(a > b) swap(a,b);
return vector<int>{a,b};
}
};