`
kmplayer
  • 浏览: 509794 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

找出数组中两个只出现一次的数字

阅读更多
1,题意:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

2,分析:
(1)各个元素依次异或,得到两个数字异或的结果 val.
(2)找到val的一个bit为1的位.
(3)根据上述比特位1或0将原来的数组分成两组.
(4)每组异或,即可得到要求的数.

3,实例代码:
#include <iostream>
#include <cstring>
using namespace std;


void findOnce(int data[], int n, int &num1, int &num2)
{
    if (n < 5)
        return;
    int r1 = 0;
    for (int i = 0; i < n; i++)
        r1 ^= data[i];
    int bitNum = 0;
    while ( !(r1 & 0x1))
    {
        r1 >>= 1;
        ++bitNum;
    }

    int  flag = (1 << bitNum);
    num1 = 0;
    num2 = 0;
    for (int i = 0; i < n; i++)
    {
        if ( data[i] & flag)
            num1 ^= data[i];
        else
            num2 ^= data[i];
    }
}

int main()
{
    int data[] = {1,1,2,3,3,4,5,5};
    int num1, num2;
    findOnce(data, sizeof(data)/sizeof(data[0]), num1, num2);
    cout << num1 <<" " << num2 << endl;
    return 0;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics