首页 > 代码库 > 找出数组中只出现一次的数
找出数组中只出现一次的数
这个题目有三种变形。
第一种，一个数组中所有数都出现了两次，只有一个数出现了一次，求这个数。这个题比较简单，只要知道数字间异或的特性，就可以很容易的得出答案。
int find_num_appear_once(int *data, int length){ if(data=http://www.mamicode.com/=NULL || length==0)return; int i=0; int res=0; for(;i<length;i++){ res ^= data[i]; } return res;}
第二种，一个数组中所有的数都出现两次，只有两个数出现了一次，求出这两个数。这个题目比较难，需要把未知问题向已知问题转化。先把所有数全部异或，得到一个数，这个数是答案中两个数异或的结果所以它一定不为0，那么把它转化为二进制数的时候一定有一位位1。通过这个数的二进制数中第一个为1的那一位将数组中的数分成两部分，那么这两部分就是问题一里的情况了，分别再用问题一的方法把答案找出来。
int *find_num_appear_once(int *data, int length){ if(data=http://www.mamicode.com/=NULL || length<2)return; int i=0; int j=0; int temp=0; int res[2]={0}; for(;i<length;i++){ temp ^= data[i]; } unsigned int index=find_first_index(res); for(;j<length;j++){ if(is_bit_one(index, data[j])){ res[0] ^= data[j]; }else{ res[1] ^= data[j]; } } return res;}unsigned int find_first_index(int num){//找到第一个为1的位 int index_bit=0; while((num&1)==0 && index_bit<32){ num>>1; index_bit++; } return index_bit;}bool is_bit_one(unsigned int num1, int num2){//判断一个数的num1位是否为1 int num = num2>>num1; return (num&1);}
第三种，一个数组中所有的数都出现过三次，只有一个数出现过一次，求这个数。这个题目的解决办法是通过将这个数组中数字的每一位相加再与3取余数，这样这个余数不是1就是0。再将这个余数放置到相应位上（是通过数组中数的第几位得到的余数就放在第几位），这样就可以重组出那个单一的数。
int *find_num_appear_once(int *data, int length){ if(data=http://www.mamicode.com/=NULL || length==0)return; int i=0; int j=0; int res=0; int num=0; for(;i<32;i++){ num=0; for(j=0;j<length;j++){ num += (data[j]>>i)&1;//循环完成，num存储了在这个位上一共有多少个1 } res |= (num%3)<<i; } return res;}
找出数组中只出现一次的数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。