力扣260题 (只出现一次的数字3)
依然用之前提到过的第一种方法写了一下,略微改动了一下。
代码如下:
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
map<int,int>hashmap;
int i=0;
vector<int>result;
for(vector<int>::iterator iter =nums.begin();iter!=nums.end();iter++)
{
if(hashmap.find(*iter)!=hashmap.end())
hashmap[*iter]+=1;
else
hashmap.insert(make_pair(*iter,1));
}
for(map<int,int>::iterator iter1=hashmap.begin();iter1!=hashmap.end();iter1++)
{
if((iter1->second)==1){
result.push_back(iter1->first);
// return result;
}
else //result=0;
}
return result;
}
};
依旧运行的很慢,所以还是要用位运算来实现一下。
然后参考了一个大神的博客,放在这里。
LeetCode 260 Single Number III
然后记录一下我自己的分析:
整体的思路就是先把所有的数都异或一遍,因为其中有两个数是不同的,所以异或之后,一定存在一位数为1。
这个时候由于异或是 不同为1,也就是说,这两个数在这一位是不同的,必定一个是0,一个是1。
然后就可以根据这个位,将原来数组的数分成两组,一组是这一位是0的数,一组是这一位是1的数(这两个出现一次的数也分进去)。
最后分别在不同的组分别进行异或,就得出了这两个数。
for example:
将大神的代码搬到这来。
bool IsBit1(int num, unsigned int index) {
num = num >> index;
return (num & 1);
}
unsigned int FindFirstBigIs1(int num) {
int indexBit = 0;
while (((num & 1) == 0) && (indexBit < 8 * sizeof(int))) {
num = num >> 1;
++indexBit;
}
return indexBit;
}
vector<int> singleNumber(vector<int>& nums) {
vector<int> singleV;
if (nums.size() <= 0) return singleV;
int resultExclusiveOR = 0;
for (int i = 0; i < nums.size(); ++i)
resultExclusiveOR ^= nums[i];
unsigned int indexOf1 = FindFirstBigIs1(resultExclusiveOR);
int singleNum1 =0, singleNum2 = 0;
for (int j = 0; j < nums.size(); ++j) {
if (IsBit1(nums[j], indexOf1))
singleNum1 ^= nums[j];
else
singleNum2 ^= nums[j];
}
singleV.push_back(singleNum1);
singleV.push_back(singleNum2);
return singleV;
}