Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = ;
int nums_size = nums.size();
for(int i=;i<nums_size;i++){
res ^= nums[i];
}
return res;
}
};
Single Number II
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
统计各个二进制位中1的个数,该方法适用于这种类型的题目：数组中的所有数都出现了K次，只有一个数只出现了一次
const int BITS = sizeof(int) * ;
class Solution {
public:
int singleNumber(vector<int>& nums) {
int times[BITS]={};
cout<<BITS<<endl;
int nums_size = nums.size();
for(int i=;i<nums_size;i++){
int x = nums[i];
for(int j=;j<BITS;j++){
if((x>>j) & ){
times[j]++;
}
}
}
int res = ;
for(int i=;i<BITS;i++){
if(times[i]%){
res += <<i;
}
}
return res;
}
};
Single Number III
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
- The order of the result is not important. So in the above example,
[5, 3]is also correct. - Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity
所有的结果异或之后剩下一个非零值，这个值就是只出现一次的两个数的异或结果，找到这个数中第一个bit=1的数位，用1左移这么多个数位做为数组的分割器。
const int BITS = sizeof(int)*;
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int nums_size = nums.size();
int n = ;
for(int i=;i<nums_size;i++){
n ^= nums[i];
}
int seprator = ;
for(int i=;i<BITS;i++){
if((n>>i) & ){
seprator = <<i;
break;
}
}
vector<int> res;
int res1=,res2=;
for(int i=;i<nums_size;i++){
if( (seprator & nums[i])){
res1 ^= nums[i];
}else{
res2 ^= nums[i];
}
}
res.push_back(res1);
res.push_back(res2);
return res;
}
};