当前位置：首页 > news >正文

求数组中只出现一次的数字（算法）

news 来源：原创 2024/4/29 4:53:25

　　首先，我们先考虑简单的情况下，就是只有一个出现一次的数字，其余数字都出现2次，这样我们可以采用一种很巧妙的方法：“异或”。

void findNumAppearOnce(int date[],int length,int &num)
{
       if(length<2)
              return;
        num=0;
        for(int i=0;i<length;i++)
       {
              num ^=date[i];
       }
}

　然后，我们考虑有两个出现一次的数字的情况。同理，我们依然采用上面的方法，由于两个出现一次的数字肯定不相同，最后的结果就是这两个数字的异或结果，因而这个结果必不为0，至少存在一位为1（就是由于这两个出现一次的数字的同一位上：一个为0，一个为1）。因此，我们首先找到一位不为0的二进制位n，把所有的数据按照此位划分为两组，这两组的第n位分别为0和1，这样就能保证每组中必然包含一个仅出现一次的数字。

　　源代码参考：剑指Offer

　　代码如下：

#include <iostream>
using namespace std;
//从左向右移动，获取第一个为1的位数
unsigned int FindFirstBitIs1(int num)
{
    int indexBit = 0;
    while(((num&1)==0)&&(indexBit<32))
    {
        num=num>>1;
        ++indexBit;
    }
    return indexBit;
}
//对数据分组
bool IsBit1(int num,unsigned int indexBit)
{
    //移动相应的位数，让相对位置移动到最后一位上
    num=num>>indexBit;
    //例如：1001101 ^ 0000001 这样的情况为0 ; 1010110 ^ 0000001 这样的情况为1
    return (num & 1);
}

void findNumAppearOnce(int date[],int length,int &num1, int &num2)
{    
    if (length<2)
        return;

    //get num1^num2
    int resultExclusiveOR = 0;
    for (int i=0;i<length;i++)
        resultExclusiveOR ^=date[i];
    
    unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);

    num1=0;num2=0;
    for (int j=0;j<length;j++)
    {
        if(IsBit1(date[j],indexOf1))
            num1 ^=date[j];
        else
            num2 ^=date[j];
    }
    
}

int main(int argc,char* argv[])
{
    int a[6];
    for(int i=0;i<6;i++)
        cin>>a[i];
    
    int num1,num2;
    findNumAppearOnce(a,6,num1,num2);
    cout<<"num1="<<num1<<endl;
    cout<<"num2="<<num2<<endl;
    return 0;
}