【剑指offer】数组中只出现一次的两个数字(数组)
程序员文章站
2022-03-08 16:23:40
...
题目描述:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
1.hash
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
//遍历一遍数组,用map记录出现的次数,然后再遍历一遍数组,找出出现1次的数字。
unordered_map<int, int> hash;
for (auto x : data) hash[x] ++;
vector<int> num;
for (auto x : data) {
if (hash[x] == 1) {
num.push_back(x);
}
}
*num1 = num[0];
*num2 = num[1];
}
};
2.异或
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
//异或^
// x ^ x = 0
// x ^ 0 = x
// x ^ y = z
int sum = 0;//num1^ num2
for(auto x : data) sum ^= x;
//怎么拆分
//二进制表示中一定有一位存在不同 1 0
int k = 0;
*num1 = 0;
while(!(sum >> k & 1)) k ++;//通过第k位是否为1分组
for(auto x : data)
if(x >> k & 1)
*num1 ^= x;//num1
*num2 = sum ^ *num1;// num1^num2^num1 = num2
}
};
3.自己写的low代码
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2)
{
int n=data.size();
vector<int> num;
for(int i=0;i<n;i++){
int count=0;
for(int j=0;j<n;j++){
if(data[i]==data[j]) count++;
}
if (count==1) {
num.push_back(data[i]);
}
}
*num1=num[0];
*num2=num[1];
}
};
推荐阅读