[小米] 异形数

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

[小米] 异形数

楚兴 发布时间:2015-06-23 17:22:00 浏览493 评论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;
}
【云栖快讯】云栖专辑 | 阿里开发者们的20个感悟,一通百通  详情请点击

网友评论