[小米] 异形数

  1. 云栖社区>
  2. 博客列表>
  3. 正文

[小米] 异形数

楚兴 2015-06-23 17:22:00 浏览443 评论0

摘要: 在一个长度为n的整形数组a里,除了三个数字只出现一次外,其他的数字都出现了2次。请写程序输出任意一个只出现一次的数字,程序时间和空间复杂度越小越好。 例如: a = {1,3,7,9,5,9,4,3,6,1,7},输出4或5或6。 解题思路 如果只有一个只出现一次,将所有数做异或运算,返回其值。 如果有两个数只出现一次,假设为a和b,全部数做异或运算的结果为x=a^

在一个长度为n的整形数组a里,除了三个数字只出现一次外,其他的数字都出现了2次。请写程序输出任意一个只出现一次的数字,程序时间和空间复杂度越小越好。 例如: a = {1,3,7,9,5,9,4,3,6,1,7},输出4或5或6。

解题思路

  • 如果只有一个只出现一次,将所有数做异或运算,返回其值。
  • 如果有两个数只出现一次,假设为a和b,全部数做异或运算的结果为x=a^b,由于a和b不相等,所以x不为0。从右向左扫描第一个为1的位,根据该为是否为1,将原数组分为两组,再对每组数据按情况一处理。
  • 对于有三个数只出现一次的情况,可以根据三个数两两异或,最低位有两个相同,有一个不同来求解。

实现代码

#include <iostream>
using namespace std;

int lowbit(int x);
int find(int *num, int len);

int main()
{
    int num[] = {1,1,2,2,3,3,4,4,5,6,7};
    cout<<find(num, sizeof(num)/sizeof(num[0]))<<endl;

    return 0;
}

//找出从右到左第一个出现1的位置
int lowbit(int x)
{
    return x & ~(x - 1);
}

int find(int *num, int len)
{
    int xors = 0;
    for (int i = 0; i < len; i++)
    {
        xors ^= num[i];
    }

    //三个数两两异或,最低位有两个相同,有一个不同
    int low = 0;
    for (int i = 0; i < len; i++)
    {
        //表示的是low = lowbit(a^b) ^ lowbit(a^c) ^ lowbit(b^c)
        low ^= lowbit(xors ^ num[i]);
    }

    int result = 0;
    for (int i = 0; i < len; i++)
    {
        if (lowbit(xors ^ num[i]) == low)
        {
            result ^= num[i];
        }
    }

    return result;
}
【云栖快讯】你想见的Java技术专家都在这了,向大佬提问,有问题必答  详情请点击

网友评论

楚兴
文章356篇 | 关注4
关注
为金融行业提供量身定制的云计算服务,具备低成本、高弹性、高可用、安全合规的特性。帮助金融客户... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航