Single Number III
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?
Credits:
Special thanks to for adding this problem and creating all test cases.
主要的问题是怎么把两个只有一个数的A和B分开。
如果全部异或的话得到的结果就是A^B。
A!=B,所以异或的结果中必然存在1,那么为1的那一位对应的A和B必然一个是1,一个是0,这个就可以将所有数字分为两类。
分别异或就能达到两个值了。
获取A,B最后不同的一位的方法是mask=AxorB & (~AxorB-1))。
1 class Solution { 2 public: 3 vector singleNumber(vector & nums) { 4 vector result; 5 if(nums.size()<2) return result; 6 int AxorB = 0; 7 for(int i=0;i