Question

数组中出了一个数字出现两次，其余数字都出现四次，怎样找出出现两次的数字？用java实现。

Answer 1

利用 MAP,数值设置为KEY,当有重复的时候 VALUE+1 最后循环过滤一下即可

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;


public class Test {
	public static void main(String[] args) {
		int[] nums=new int[]{1,1,1,1,2,2,3,3,3,3,4,4};
		Map<Integer,Integer> map=new HashMap<Integer,Integer>();
		for(int i=0;i<nums.length;i++){
			Integer num=map.get(nums[i]);
			if(num!=null){
				map.put(nums[i],++num);
			}else{
				map.put(nums[i],1);
			}
		}
		int n=2; //设置输出指定次数的值
		Iterator<Entry<Integer,Integer>> ite=map.entrySet().iterator();
		while(ite.hasNext()){
			Entry<Integer,Integer> entry=ite.next();
			if(entry.getValue() == n){
				System.out.println("出现次数为"+n+"次的数字有:"+entry.getKey());
			}
		}
	}
}

Answer 2

把4k+2个数看成二进制

统计每一位2进制1的个数和0的个数
因为有只有一个数出现了2次，对于二进制第 i 位统计的0/1个数，要么0的个数不能整除4，要么1的个数不能整除4,。不能整除就是你要求的数在这一位2进制的值。

通过这个方法可以求出每一位二进制的值，就ok了

时间复杂度是O(32*n),空间复杂度是O(1),应该已经是题目说的时间复杂度和空间复杂度尽可能小的那种最优的解法了，你懂的。