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的异或就可求得只出现一次的那两个数。
代码如下：
复制代码
值得注意的是：：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class 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; } };
复制代码
1(resultExclusive&1)==0)
复制代码
1(resultExclusive&1)一定要加（），否则因为==的优先级高于&,会导致while循环无法进入！！！！
最后
以上就是背后御姐最近收集整理的关于数组中出现一次的两个数 leetcode Single Number III的全部内容，更多相关数组中出现一次的两个数内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复