概述
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
- The order of the result is not important. So in the above example,
[5, 3]is also correct.
- Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
解题思路：有一个数组，其中只有两个数出现一次，其他数均出现两次，求出这两个数。参考signal number的第二种解法：http://blog.csdn.net/sinat_24520925/article/details/45576735
我们将这个数组分成两个数组，每个数组中都只有一个元素出现一次。也就是先异或所有元素，得到resultExclusive，找到resultExclusive中二进制表示的由右向左的第一位1，则表明数组中有一个一次出现的数该位的值不同，一个为0、另一个为0.下面就好做了，将数组中该位均为0的异或，均为1的异或就可求得只出现一次的那两个数。
代码如下：
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> res;
if(nums.size()==0) return res;
res.push_back(0);
res.push_back(0);
int resultExclusive=0;
for(int i=0;i<nums.size();i++)
resultExclusive^=nums[i];
int indexof1=0;
while(((resultExclusive&1)==0)&&(indexof1<8*sizeof(int)))
{
resultExclusive=resultExclusive>>1;
++indexof1;
}
for(int i=0;i<nums.size();i++)
{
if((nums[i]>>indexof1)&1==1)
res[0]^=nums[i];
else
res[1]^=nums[i];
}
return res;
}
};(resultExclusive&1)==0)(resultExclusive&1)一定要加（），否则因为==的优先级高于&,会导致while循环无法进入！！！！最后
以上就是背后御姐为你收集整理的数组中出现一次的两个数 leetcode Single Number III的全部内容，希望文章能够帮你解决数组中出现一次的两个数 leetcode Single Number III所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复