我是靠谱客的博主 坦率酸奶,这篇文章主要介绍数组中只出现一次的数字,现在分享给大家,希望可以做个参考。

题目描述

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

链接:https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
来源:牛客网

首先:位运算中异或的性质: 两个相同数字异或=0一个数和0异或还是它本身

只有一个数出现一次时,我们把数组中所有的数,依次异或运算,最后剩下的就是落单的数,因为成对儿出现的都抵消了。

依照这个思路,我们来看两个数(我们假设是AB)出现一次的数组。我们首先还是先异或,剩下的数字肯定是A、B异或的结果, 这个结果的二进制中的1,表现的是A和B的不同的位。我们就取第一个1所在的位数,假设是第3位,接着把原数组分成 两组,分组标准是第3位是否为1。如此, 相同的数肯定在一个组,因为相同数字所有位都相同,而不同的数, 肯定不在一组。然后把这两个组按照最开始的思路,依次异或,剩余的两个结果就是这两个只出现一次的数字。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*异或方法*/ class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { if(data.size()<2) return; int flag=1,sum=0; for(int i=0; i<data.size(); ++i) { sum^=data[i]; } while((sum&flag)==0) flag=flag<<1; *num1=0; *num2=0; for(int i=0; i<data.size(); ++i) { if((flag&data[i])==0) *num1^=data[i]; else *num2^=data[i]; } } };


方法二:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 哈希表,利用map存储*/ /* class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { if(data.size()<2) return; map<int,int> mapdata; vector<int> vi; for(int i=0; i<data.size(); ++i) mapdata[data[i]]++; for(int i=0; i<data.size(); ++i) { if(mapdata[data[i]]==1) vi.push_back(data[i]); } *num1=vi[0]; *num2=vi[1]; } }; */





最后

以上就是坦率酸奶最近收集整理的关于数组中只出现一次的数字的全部内容,更多相关数组中只出现一次内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(58)

评论列表共有 0 条评论

立即
投稿
返回
顶部