[小米] 异形数

2024-06-05 08:48

文章标签 小米异形

本文主要是介绍[小米] 异形数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在一个长度为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;
}