【位运算】--- 进阶题目赏析
Welcome to 9ilk's Code World
(๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏： 算法Journey
本节我们来赏析位运算的一些进阶题目。
🏠 只出现一次的数字II
📌 题目解析
只出现一次的数字II
📌 算法原理
✏️ 思路一:哈希表+异或
由题目意思可得,除了只出现一次的数字之外,其他数字都出现了三次,我们可以利用哈希表,我们遍历一遍数组,将这些数异或用ret记录,当某个数出现三次时,我们再用ret异或这个数,最后得到的结果就是只出现一次的数字,因为其他数字在我们操作下都出现了四次被异或为0。
参考代码：
class Solution {
public:int singleNumber(vector<int>& nums){unordered_map<int,int> hash;int ret = 0; for(const auto& e : nums){hash[e]++;ret ^= e;if(hash[e] == 3) //出现三次再次异或ret ^= e;} return ret; }
};✏️ 思路二: bit位分组
由于其他数字都出现3次,因此我将数组中每个数特定bit位相加,对于出现过三次的这些数,他们特定bit位相加得到的一定是3的倍数,%3得到0,最后数组中所有数加完后再%3得到的一定是只出现一次那个数字上的bit位的数字.因此,我们可以不断向左移,对每个bit位进行这样的操作,就能得到只出现一次数字的完整bit位了.
参考代码:
class Solution {
public:int singleNumber(vector<int>& nums){ int ret = 0;for(int i = 0 ; i < 32 ; i++){int sum = 0;for(int x : nums){if((x>>i)&1) sum++;}sum %= 3;//得到的是只出现一次数字i位上的数字if(sum == 1) ret |= (1 <<i);}return ret; }
};拓展 : 如果其他数出现n次,另外一个数字出现m次,我们同样可以利用这种方式来找出不同点(%n)从而来找到只出现一次的数字.
🏠 只出现一次的数字III
📌 题目解析
只出现一次的数字III
-2^31 <= nums[i] <= 2^31 - 1 注意数据范围过大使用int可能会导致数据溢出。
📌 算法原理
由图中我们可以知道，ret最后一定是两个只出现一次的数字(记为a和b)的异或，由于异或是相同为0，相异为1，因此我们可以利用n&(-n)提取异或后的ret最右边的1，也就是a和b在这个bit位上的数字不同，依照这个不同可以将原数组中的数字划分为两种：一种是k位上是1，一种是k位上是0，由于其他数字出现了两次他们异或之后得到的一定是0，最后ret1和ret0得到的一定是只出现一次的两个数字。
参考代码：
class Solution
{
public:typedef long long ll;vector<int> singleNumber(vector<int>& nums){ll ret = 0;for(int i = 0 ; i < nums.size() ; i++){ret ^= nums[i]; //得到的是两个不同的数异或}//我们先找ret最右边的1因为异或相异为1 这样就可以依照这个把a分到这一位上有0/1,b分到这一位有1/0ll k = ret & (-ret);//用k判断某一位是1还是0ll ret1 = 0;ll ret0 = 0;for(int i = 0 ; i < nums.size();i++){if(nums[i] & k) //说明该位上为1ret1 ^= nums[i];elseret0 ^= nums[i];}return {(int)ret1,(int)ret0};}
}s2;🏠 消失的两个数字
📌 题目解析
消失的两个数字
📌 算法原理
这道题其实就是丢失的数字 + 只出现一次的数字III。我们可以通过nums的数组长度知道未消失前数字的总数。异或一遍原来数字再异或一遍nums，就可以得到消失两个数字的异或。此时就转化为只出现一次的数字III，可以利用ret&(-ret)提取两者不同的bit位，依据不同再遍历一遍进行分组得到这两个数字。
参考代码：
class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int n = nums.size() + 2;int ret = 0;for(int i = 1 ; i <= n ; i++){ret ^= i;} for(auto& e : nums){ret ^= e;}// 1^4int k = ret & (-ret); //提取最右边的一个1 消失的两个数在第k位不同int ret1 = 0;int ret0 = 0;for(int i = 1 ; i <= n ; i ++){if(i & k)ret1 ^= i;elseret0 ^= i; }for(auto& e : nums){if(e & k)ret1 ^= e;elseret0 ^= e; }int max = 0;int min = ret0 > ret1 ? (max = ret0,ret1) : (max = ret1,ret0);return {min,max};}
};完。