本文最后更新于:2020年4月28日 下午

地址: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;
    }
};