位图算法经典剖析（未完）

位图算法经典剖析（未完）"/>

位图算法经典剖析（未完）

第一题 只出现一次的数字||

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:int singleNumber(vector<int>& nums) {int ret=0;for(int i=0;i<32;i++)//第i位{int sum=0;//该位1的和for(int j=0;j<nums.size();j++)//第j个数字{if( ( (nums[j] >> i) & 1) == 1) ++sum;}sum%=3;if(sum)ret=(1<<i) | ret;}return ret;}
};

第二题 两整数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

/

class Solution {
public:int getSum(int a, int b) {while(a != 0)//把a当做进位{int carry = (a & b) <<1;//找到进位b=a^b;//(无进位相加处理)a=carry;//(存储进位信息，循环无进位相加，直到被加的数等于零。)}return b;}
};

第三题 消失的两个数字

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

只能处理有序数组

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int now=1,a[2]={0};int q=0;for(auto e: nums){cout<<e<<endl;}while(now<nums[0]){if(q>=2) return {a[0],a[1]};a[q++]=now;now++;}if(q>=2) return {a[0],a[1]};for(int i=0;i<nums.size()+2;i++){if(q>=2) return {a[0],a[1]};if(i>=nums.size())//越界了还没找到{while(q<2) a[q++]=now++;break;}if(now != nums[i]){int tmp=i;while(now != nums[i])//连续的情况{a[q++]=now++;if(q>=2) return {a[0],a[1]};}now++;}else now++;}return {a[0],a[1]};}
};

可以排序一下

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int now=1,a[2]={0};int q=0;sort(nums.begin(),nums.end());while(now<nums[0]){if(q>=2) return {a[0],a[1]};a[q++]=now;now++;}if(q>=2) return {a[0],a[1]};for(int i=0;i<nums.size()+2;i++){if(q>=2) return {a[0],a[1]};if(i>=nums.size())//越界了还没找到{while(q<2) a[q++]=now++;break;}if(now != nums[i]){int tmp=i;while(now != nums[i])//连续的情况{a[q++]=now++;if(q>=2) return {a[0],a[1]};}now++;}else now++;}return {a[0],a[1]};}
};

位运算解法最优

        int tmp=0;for(auto e : nums){tmp^=e;}for(int i = 1;i<=nums.size()+2;i++){tmp^=i;}//现在tmp中存的是a^bint diff=0;while(diff<32){if( ((tmp>>diff) & 1)==1) break;diff++;}int a=0,b=0;//记得初始化for(auto e :nums){if(((e>>diff) & 1)==1) a^=e;else b^=e; }for(int i=1;i<=nums.size()+2;i++)//小于等于漏了{if(((i>>diff) & 1)==1) a^=i;else b^=i;             }return {a,b};