剑指offer——数组中只出现一次的两个数字（c++)

56 阅读 0 评论 37 点赞

我是靠谱客的博主温柔发夹，最近开发中收集的这篇文章主要介绍剑指offer——数组中只出现一次的两个数字（c++)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请找出这两个只出现一次的数字。
你可以假设这两个数字一定存在。
样例

输入：[1,2,3,3,4,4]
输出：[1,2]

思路

将原数组分成两个子数组，使得每个数组包含一个只出现一次的数字，而其他数字出现两次，这样对两个子数组分别异或，就能找到这两个数字。从头到尾异或数组中的每个数字，得到的结果肯定不为0，也就是说，这个数的二进制表示中至少有一位为1；
我们在结果数字中找出这个位置，记为n。现在以第n位是不是1为标准将数组分成两个子数组。这样做的道理在于第n位为1的话，两个出现一次的数在这一位上肯定不同，这样才能将两者分开。
举例来说，{2， 4， 3， 6， 3， 2， 5， 5}，异或结果为0010，倒数第二位为1，分成两个子数字为
{2， 3， 6， 3， 2}，以及{4， 5， 5}。然后分别对这两个子数组求异或，就能找出这两个只出现一次的数字{6, 4}。

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        vector<int> res;
        if(nums.size() < 2)
            return res;
        int resAll = 0;
        for(int i = 0; i < nums.size(); ++i)
            resAll ^= nums[i];
        unsigned int index1 = firstBits1(resAll);
        int num1 = 0, num2 = 0;
        for(int i = 0; i < nums.size(); ++i){
            if(isBit1(nums[i], index1))
                num1 ^= nums[i];
            else
                num2 ^= nums[i];
        }
        res.push_back(num1);
        res.push_back(num2);
        return res;
    }
private:
    unsigned int firstBits1(int num){
        int index = 0;
        while((num & 1) == 0 && (index * 8 < sizeof(int))){
            num = num >> 1;
            ++index;
        }
        return index;
    }
    bool isBit1(int num, int index){
        num = num >> index;
        return (num & 1);
    }
};