欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-15 10:44:38
...

题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字
分析:如果让我来解的话,我首先想到的尽可能效率高的方法是用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);
    }
};