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

牛客网刷题|数组中只出现一次的数字

程序员文章站 2022-03-01 13:33:14
...

题目来源:牛客网

编程连接

题目描述

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

题目解析:

使用异或,两个相同的数字异或会等于0;
若只存在一个数,一直异或就会把这个数生下来;
若两个数,一直异或,这两个不同的数异或之后会生成一个数,某位上一定会出现1,则表示这个位上,两数不同;根据这个位,将数组分成两组,每组即只存在一个不同的数。

代码:

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.size()<2)
            return;
        int index = data[0];
        for(int i=1; i<(int)data.size(); i++)
        {
            index ^= data[i];
        }
         if(index==0)
           return ;

        int nbit = Getbit(index);

        for(int i =0;i<(int)data.size();i++)
        {
            if(isbit(data[i],nbit))
            {
                * num1 ^= data[i];
            }
            else
            {
                * num2 ^= data[i];

            }
        }      
    }

    int Getbit(int num)
    {
        int index = 0;
        while((num&1)==0)
        {
            index++;
            num = num>>1;
        }
        return index;
    }

    bool isbit(int num,int index)
    {
        num = num>>index;
        return num&1;
    }
};