【一天一道LeetCode】#260. Single Number III

一天一道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

上一篇:eclipse使用和快捷键


下一篇:【JAVA】高并发优化细节点