LeetCode Single Number III （xor）

题意：

　　给一个数组，其中仅有两个元素是出现1次的，且其他元素均出现2次。求这两个特殊的元素？

思路：

　　跟查找单个特殊的那道题是差不多的，只是这次出现了两个特殊的。将数组扫一遍求全部元素的异或和 x，结果也就是这两个特殊的元素的异或和了。现在必须找到两个当中的一个，才能恢复出另外一个。注意到x的二进制位中必定有1，那么只需要找到其中任意一个1对应的整数，再将数组中所有该位为1的计算他们的异或和a，a就是结果了，而另一个数b=x^a。

 vector<int> singleNumber(vector<int>& nums) {

     int x=;

     for(int i=; i<nums.size(); i++)    x^=nums[i];

     int lowbit=x-(x&(x-)), a=;

     for(int i=; i<nums.size(); i++)

         if( lowbit & nums[i] )    a^=nums[i];

     return vector<int>{a,x^a};

 }

AC代码

巴特西

LeetCode Single Number III （xor）

最新文章

热门文章