LeetCode 面试题56 数组中数字的出现次数

这道题是给出你一个数组，只有两个数字出现一次，其余数字都是出现两次，要求空间O(1),时间O(n)。这道题的做法非常巧，我只想到了两个相同的数异或为0，然后把所有的数异或之后就得出目标两个数异或的结果，后面就不知道怎么才能在题目给出的时间和空间复杂度完成。我看了一个很好的方法，假设所有数的异或结果为10100，那么结果的两个数在从右往左数第三位不相同，我们就可以把数组中的数分为两组，一组是从右往左数第三位为0，一组是不为0，这两个只出现一次的数必然分别在这两组中，再分别求这两组中所有的数的异或结果，最终的结果就是两个只出现一次的数。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        vector<int> ans;
        int sz=nums.size();
        int t=0;
        for(int i=0;i<sz;i++)
            t^=nums[i];
        int k=0;
        for(int i=0;;i++)
        {
            if((t&(1<<i))!=0)
            {
                k=1<<i;break;
            }
        }
        int t1=0,t2=0;
        for(int i=0;i<sz;i++)
        {
            if((nums[i]&k)!=0) t1^=nums[i];
            else t2^=nums[i];
        }
        ans.push_back(t1);
        ans.push_back(t2);
        return ans;
    }
};

LeetCode 面试题56 数组中数字的出现次数

原文：https://www.cnblogs.com/ambition-hhn/p/12797582.html