牛客算法刷题-BM52 数组中只出现一次的两个数字

描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

数据范围：2$\le$n$\le 1000$，数组中每个数的大小0$\le$n$\le 1000000$。

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

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

示例1

输入：[1,4,1,6]
返回值：[4,6]
说明：返回的结果中较小的数排在前面

示例2

输入：[1,2,3,3,2,9]
返回值：[1,9]

思路：
对于查找类的题目，可以先思考用哈希表的方式来解决，对于数组中的数字，进行哈希表查找，如果找到了，则哈希表中的元素个数+1，最后从哈希表中返回元素个数=1的键(key)。

 /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        map<int,int>hash;//定义hashmap，hashmap中会自动进行升序排序
        vector<int>res;
        int count=1;
        for(int i=0;i<array.size();i++)
        {
         
              if(hash.find(array[i])==hash.end())//未找到对于key值
              {
                hash[array[i]]=1;//将[键，值]添加进hashmap中
                
              }
              else
              {
                hash[array[i]]=hash[array[i]]+1;//如果找到了键，则元素value+1
              }
             // cout<< array[i]<<" "<<hash[array[i]]<<endl;
            
        }
 
        for(int i=0;i<array.size();i++)
        {
            if(hash[array[i]]==1)//判断当元素value是否=1
            {
                
                res.push_back(array[i]);
            }
        }
        sort(res.begin(),res.end());//排序输出

        return res;
    }