【剑指offer】数组中只出现一次的数字
数组中只出现一次的数字
http://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
题目描述
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
1、思路分析
用HashMap存储每个元素及其对应出现的次数,最后再遍历HashMap即可。看到评论区有人用异或运算来做,也十分巧妙。
2、代码
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array.length < 2) return;
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < array.length; i++) {
Integer key = array[i];
Integer value = map.get(key);
if(value == null)
map.put(array[i],1);
else
map.put(array[i],value+1);
}
int index = 0; // 标志是第几个出现两次的数
for(int i = 0; i < array.length; i++) {
if(map.get(array[i]) == 1 && index == 0) {
num1[index] = array[i];
index++;
}
else if(map.get(array[i]) == 1 && index == 1) {
num2[index-1] = array[i];
break;
}
}
}
}
查看11道真题和解析