数组中只出现一次的数字 I（C++）(其他数字出现两次）

74 阅读 0 评论 49 点赞

我是靠谱客的博主雪白舞蹈，最近开发中收集的这篇文章主要介绍数组中只出现一次的数字 I（C++）(其他数字出现两次），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

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

思路：

如果一个数组中只有一个数字只出现了一次，那么将数组中的所有数字依次异或得到的即位该值
当数组中有两个出现一次的数字时，需要将数组分为两部分，再用上述办法找出两个数字

此时如果将整个数组异或，最终得到的是这两个不同的数字异或之后的结果；在异或结果中找到最右边的1（表示这两个数字中有1个该位为1），然后将整个数组根据该位是否为1分成两部分（相同的两个数字肯定被分到了1组，并且两个只出现一次的数字被分到了不同的部分），然后再对两部分分别异或得到两个只出现一次的数字。

代码实现：

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int len = data.size();
        if(len < 2)
            return;
        int one_or = 0;
        for(int i = 0; i < len; i++)
            one_or ^= data[i];
        int one_index = FindIndex(one_or);
        /*---根据one_index位是不是1将数组分为两部分---*/
        for(int i = 0; i < len; i++)
        {
            if(IndexIsOne(data[i], one_index))
                *num1 ^= data[i];
            else
                *num2 ^= data[i];
        }
    }
    /*---寻找二进制中最右边的1所在的位置---*/
    int FindIndex(int one_or)
    {
        int idx = 0;
        while(((one_or & 1) == 0) && (idx < 8 * sizeof(int)))
        {
            one_or = one_or >> 1;
            idx++;
        }
        return idx;
    }
    /*---判断某一位是不是1---*/
    bool IndexIsOne(int num, int idx)
    {
        num = num >> idx;
        return (num & 1);
    }
};

/*------直接将上边的过程合并----*/
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int len = nums.size();
        int temp = 0;
        for(int i = 0; i < len; i++)
            temp ^= nums[i];
        int mask = 1;
        while((mask & temp) == 0)
            mask = mask << 1;
        int num1 = 0;
        int num2 = 0;
        for(int i = 0; i < len; i++)
        {
            if(nums[i] & mask)
                num1 ^= nums[i];
            else
                num2 ^= nums[i];
        }
        vector<int> result;
        result.push_back(num1);
        result.push_back(num2);
        return result;
    }
};