Leetcode 面试题56 - I.数组中数字出现的次数【C++】

地址：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

题目

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

• 2 <= nums <= 10000

解题思路

这个题暴力解其实很简单，比如遍历数组，如果是第一次遍历到的元素，就将其加入到返回数组中，对遍历到的每一个元素，去返回数组中查找其是否已遇到过，如果返回数组中已存在，则将其从返回数组中删除，最终遍历完整个数组，则返回数组中剩下的元素即只出现过一次的元素。时间复杂度大于O(n)。

然后我想到了用集合来做同样的工作，只不过集合有 find() 函数可以直接判断集合中是否已存在某一个元素，思路都是一样的，换汤不换药。其实我觉得这么做并不是题目要求时间复杂度为O(1)的意思，不过提交还是通过了。

官方题解是用异或来做的，挺巧妙的办法，感觉一般不容易想到。

代码

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        vector<int> ans;//返回值
        set<int> ns;//存储数组中唯一的元素
        for (int i = 0; i < nums.size(); i++) {
            set<int>::iterator index = ns.find(nums[i]);
            if (index == ns.end()) {
                ns.insert(nums[i]);
            }
            else {
                ns.erase(index);
            }
        }
        //集合转数组
        for (set<int>::iterator i = ns.begin(); i != ns.end(); i++) {
            ans.push_back(*i);
        }
        return ans;
    }
};