一天一道LeetCode

本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github

欢迎大家关注我的新浪微博，我的新浪微博

欢迎转载，转载请注明出处

（一）题目

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?

（二）解题

题目大意：在一个数组中有两个数只出现过一次，其他的数都出现两次，找出这两个数

解题思路：对比【一天一道LeetCode】#137. Single Number，如果有两个只出现一次的数，那么用异或运算可以找出这两个数的异或值

从这个异或值下手，这两个数不同，那么就可以找出其中不同的位，取一个不同的位，如第M位。

将整个数组分为两类，一类为第M位为1，一类为第M类为0，这样在每一组数中只有一个只出现一次的数，很容易就用异或运算来解决了。

具体思路见代码：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> ret;
        int size = nums.size();
        if(size == 0) return ret;
        int temp = nums[0];
        for(int i = 1 ; i < size ;i++) temp^=nums[i];//求全部异或后的最终值
        unsigned int bit;
        for(int i = 0 ; i < 32 ; i++) {//找到temp中第一个为1的位
            bit= 1<<i;
            if((temp&bit)==bit) break;
        }
        int temp1 =0 , temp2 =0;//temp1为第一个只出现一次的数，temp2为第二个
        for(int i = 0 ; i < size ;i++){
            if((nums[i]&bit)==0) {//分组，第M位上为0的组
                temp1^=nums[i];
            }
            else{
                temp2^=nums[i];//第M位上为1的组
            }
        }
        ret.push_back(temp1);
        ret.push_back(temp2);
        return ret;
    }
};

相关题目：

【一天一道LeetCode】#137. Single Number II

【一天一道LeetCode】#137. Single Number