剑指Offer_面试题40_数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

分析：如果让我来解的话，我首先想到的尽可能效率高的方法是用hash表，便利一遍，得到结果；

解法一：unordered_map<int, int>, first用来保存数组int内容，second 用来统计数字，遍历之后，遍历以便unordered_map,其中second项等于1的即为所求

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        
        if(!data.empty())
        {
            unordered_map<int, int> hashmap;
            for(int num : data)
                ++hashmap[num];
            bool first = true;
            for(auto it = hashmap.begin(); it != hashmap.end(); ++it)
            {
                if(it->second == 1)
                {
                    if(first)
                    {
                        *num1 = it->first;
                        first = false;
                    }
                    else{
                        *num2 = it->first;
                        break;
                    }
                }
            }
        }
    }
};

解法二：面试官期望的标准解法，利用数组特性，数组中只有两个数字出现一次，其他出现两次。异或具有交换律和结合律，对数组所有元素进行异或 ^=, 结果就是两个相异的出现一次的数的异或结果，然后判断结果最低位1的位数index，根据index来将数组分为两个子数组，这两个数字一定分别在两个子数组中，因为他们index位相异，而其他成对的数字必定也成对出现在子数组中，然后对两个子数组分别^=,两个结果即为两个所求数字；

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.empty()) return;
        int sum = 0;
        for(int num : data)
            sum ^= num;
        int index = 0;
        while(sum)
        {
            if((sum & 1) == 1){
                break;
            }
            sum = sum >> 1;
            ++index;
        }
        (*num1) = 0, (*num2) = 0;
        for(int num : data){
            if(NumIndexIs1(num, index))
                (*num1) ^= num;
            else
                (*num2) ^= num;
        }
         
    }
    bool NumIndexIs1(int num, int index)
    {
        while(index)
        {
            num = num >> 1;
            --index;
        }
        return (num & 1);
    }
};