【剑指offer】数组中只出现一次的数

2020-12-13 15:17

阅读：371

标签：经典 == span none 数据结构现在空间 set 性能

题目描述

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

分析：

经典的异或技巧题

两个相同的数字异或的结果为0，一个数和0异或的结果是其本身，假设现在那两个不同的数字是A和B，那么将整个数组的元素依次异或得到的结果ans就是A和B的异或结果

ans的二进制中第k位的1代表A的第k位和B的第k位不同，我们现在按照第k位是否相同将原数组分成两个子数组，那么必定A和B分别分散在两个子数组中，然后将子数组依次异或，得到的结果就是A和B的值！

至于k的取值则可以去第一个1即可

时间复杂度：O(N)

空间复杂度：O(1)

若采用map/set等其他辅助数据结构则需要额外的空间，性能也肯定没有异或法快！

void FindNumsAppearOnce(vectorint> v,int *k1,int *k2)
{
    int n=v.size();
    if(n2)
        return ;
    int ans=0;

    //得到k1和k2的异或结果
    for(int i=0; i)
        ans^=v[i];

    //flag为将原数组分割成两个子数组的标志
    int flag=1;
    while((ans&flag)==0)
        flag1;

    //0异或x还是等于x
    *k1=0;
    *k2=0;

    //将子数组逐个异或得到k1和k2的值
    for(int i=0; i)
    {
        if((flag&v[i])==0)
            *k2^=v[i];
        else
            *k1^=v[i];
    }
}

【剑指offer】数组中只出现一次的数

标签：经典 == span none 数据结构现在空间 set 性能

原文地址：https://www.cnblogs.com/yinbiao/p/11577238.html

上一篇：使用NotePad++ 运行轻量级的C#代码

下一篇：java正则表达式

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【剑指offer】数组中只出现一次的数
文章链接：http://soscw.com/essay/34992.html

亲，登录后才可以留言！

【剑指offer】数组中只出现一次的数

题目描述

评论

热门文章

推荐文章

最新文章

置顶文章