136. Single Number
除了一个数字，其他数字都出现了两遍。
用异或解决，亦或的特点：1.相同的数结果为0，不同的数结果为1
2.与自己亦或为0，与0亦或为原来的数
class Solution {
public:
int singleNumber(vector<int>& nums) {
if(nums.empty())
return -;
int res = ;
for(int i = ;i < nums.size();i++)
res ^= nums[i];
return res;
}
};
137. Single Number II
除了一个数字其他数字都出现了三遍。
因为数字为int型，就有32位。统计每个位上1的个数，然后在每位取余，余下的每位的结果肯定是那个单独的数在每位的结果
https://www.cnblogs.com/grandyang/p/4263927.html
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = ;
for(int i = ;i < ;i++){
int tmp = ;
for(int j = ;j < nums.size();j++){
tmp += (nums[j] >> i) & ;
}
res |= (tmp % ) << i;
}
return res;
}
};
260. Single Number III
有两个数字都只出现了一次，其他数字都出现了两遍。
两个只出现一次的数字在所有位中肯定有一位是不同的，所以亦或出来可以将两个数分开，剩下数无论那一位是否为1肯定都是成对出现，这个时候就可以利用136. Single Number的方法单独处理两个小的数组。findFirstOne其实就是找生成的结果第一个为1的，这个index实际上可以用第几位来表达，比如返回结果3，就是第三位。但我这样处理，直接返回第三位为1，其他位为0，方便之后直接划分数组。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> result;
if(nums.empty())
return result;
int num = ;
for(int i = ;i < nums.size();i++)
num ^= nums[i];
int index = findFirstOne(num);
vector<int> nums1,nums2;
for(int i = ;i < nums.size();i++){
if(nums[i] & index)
nums1.push_back(nums[i]);
else
nums2.push_back(nums[i]);
}
int num1 = ;
for(int i = ;i < nums1.size();i++)
num1 ^= nums1[i];
result.push_back(num1);
int num2 = ;
for(int i = ;i < nums2.size();i++)
num2 ^= nums2[i];
result.push_back(num2);
return result;
}
int findFirstOne(int num){
int index = ;
int tmp = num & index;
while(!tmp){
index = index << ;
tmp = num & index;
}
return index;
}
};
剑指offer40 数组中只出现一次的数字:
错误写法：
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int length = data.size();
if(length <= )
return;
int num = ;
for(int i = ;i < length;i++){
num = num ^ data[i];
}
int number = FindFirst1(num);
vector<int> data1;
vector<int> data2;
for(int i = ;i < length;i++){
if(data[i] & number)
data1.push_back(data[i]);
else
data2.push_back(data[i]);
}
*num1 = ;
*num2 = ;
for(int i = ;i < data1.size();i++){
*num1 ^= data1[i];
}
for(int i = ;i < data2.size();i++){
*num2 ^= data2[i];
}
}
int FindFirst1(int num){
int number = ;
int res = num & number;
while(res == ){
number << ; //这里并没有对number进行更新
res = num & number;
}
return number;
}
};
正确写法：
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int length = data.size();
if(length <= )
return;
int num = ;
for(int i = ;i < length;i++){
num = num ^ data[i];
}
int number = FindFirst1(num);
vector<int> data1;
vector<int> data2;
for(int i = ;i < length;i++){
if(data[i] & number)
data1.push_back(data[i]);
else
data2.push_back(data[i]);
}
*num1 = ;
*num2 = ;
for(int i = ;i < data1.size();i++){
*num1 ^= data1[i];
}
for(int i = ;i < data2.size();i++){
*num2 ^= data2[i];
}
}
int FindFirst1(int num){
int number = ;
int res = num & number;
while(res == ){
number = number << ;
res = num & number;
}
return number;
}
};