LeetCode刷题（81）～数组中数字出现的次数【分组异或】

题目描述

一个整型数组 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.length <= 10000

解答 By 海轰

提交代码（哈希）

vector<int> singleNumbers(vector<int>& nums) {
        unordered_map<int,int> m;
        for(int num:nums)
           ++m[num];
        vector<int> res;
        for(unordered_map<int,int>::iterator it=m.begin();it!=m.end();++it)
        {
            if(it->second==1)
            res.push_back(it->first);
        }
        return res;
    }

运行结果

解答

Demo（分组异或：思路）

vector<int> singleNumbers(vector<int>& nums) {
       int sum=0;
       for(int num:nums)
       sum^=num;
       int temp=sum&(-sum);// 取sum最后边的1
       int a=0;
       int b=0;
       for(int num:nums)
       {
           if(temp&num) 
           a^=num;
           else
           b^=num;
       }
       return {a,b};
    }

运行结果

算法

1. 先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
2. 在异或结果中找到任意为 1 的位。
3. 根据这一位对所有的数字进行分组。
4. 在每个组内进行异或操作，得到两个数字

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof