【剑指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; } } } }