数组中出现一次的数字
数组中只出现一次的数字
http://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路分析:
解法一:通过hashMap记录每个数组元素出现的次数,最后再遍历一遍数组,找出出现次数为1的数值
解法二:所有的数组元素异或的结果为出现一次的两个数字的异或的结果result,然后通过result &=-result 把原数组中分为两个数组 每个数组元素的异或结果就为出现一次的数字
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int length = array.length;
if(array == null || length == 0){
return;
}
int result = 0;
for(int i=0;i < length;i++){
result^=array[i];
}
result &= -result; //得到两个出现一次数字的倒数第一个
for(int i = 0; i < length; i++){
if((result & array[i]) == 0){
num1[0] ^= array[i];
}else{
num2[0] ^= array[i];
}
}
}
}
查看11道真题和解析