题解

题目

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 数据范围：数组长度2≤n≤1000，数组中每个数的大小 0<val≤1000000

要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

提示：输出时按非降序排列。

思路

一看到这个数组中只出现几次的情况，我就立马想到了HashSet，为什么不是TreeSet或者是TreeMap其他的呢，因为HashSet有一个功能contains()，可以判断HashSet中是否含有某个key，那么我们只要遍历这个数组，一一判断HashSet中是否含有，若没有则添加，若有则删除。最后只要将这个set转为数组即可。

HashSet是根据哈希来检索的，所以速度很快，像list集合也是有contains()方法，但是list是将数组从头到尾遍历一次，很明显检索的速度不如HashSet。

代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i : array){
            if(!set.contains(i)){
                //set集合不包含这个i，添加进集合
                set.add(i);
            }else{
                set.remove(i);
            }
        }
        int[] arr = new int[2];
        int i=0;
        for(int a : set){
            arr[i++] = a;
        }
        
        return arr;
    }
}