leetcode 136. Single Number 、 137. Single Number II 、 260. Single Number III(剑指offer40 数组中只出现一次的数字)

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;
}
};
上一篇:剑指offer——数组中出现次数超过一半的数字(c++)


下一篇:菜鸟学Android编程——简单计算器《一》