首页 > 代码库 > 面试题---找出数组中两个只出现一次的数
面试题---找出数组中两个只出现一次的数
题目描述：给一个数组，里面有两个数只出现一次，其它的数都出现两次，请找出这两个数；
样例：输入 2 4 2 7 4 9
输出 7 9
思路：假定要找出的这两个数为x、y 把所有的数异或，结果是x与y异或的值，那么肯定不为0，那么这个值的二进制至少有一位为1，也就是说x和y的二进制在这一位上必定一个为0，一个为1，那么可以根据这一位把这个数组分成两个数组，x和y在不同的数组里，接下来对每个数组直接异或出的值就是结果了；
代码如下：
#include <iostream>#include <cstdio>using namespace std;int num1,num2;int singleNumber(int nums[],int length){ num1=num2=0; if(length<2) return -1; int re=0; for(int i=0;i<length;i++) re^=nums[i]; int ind=0; while((re&1)==0&&(ind<8*sizeof(int))) { re=re>>1; ++ind; } for(int j=0;j<length;++j) { int t=(nums[j]>>ind)&1; if(t) num1^=nums[j]; else num2^=nums[j]; }}int main(){ int nums[100]={2,4,2,7,4,9}; singleNumber(nums,6); cout<<num1<<" "<<num2<<endl; return 0;}
面试题---找出数组中两个只出现一次的数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。