力扣leetcode剑指 Offer 56 - I. 数组中数字出现的次数C++

剑指 Offer 56 - I. 数组中数字出现的次数
剑指 Offer 56 - I. 数组中数字出现的次数

经过前面两道题目的训练，相信很多人一看到题目就想到了使用位运算来进行求解，但是如何恰当地使用位运算和在何处使用位运算成为了一个难点

我们来观察题目，首先可以看到一个数组中除了两个数字之外其余数字都出现了两次，我们考虑前面做过的第一道题目，如果是只有一个数字出现了一次的话，那么我们呢可以轻松地利用逐元素异或的思想，那么如何把问题转化为数组中只有一个出现一次的元素呢 我们需要想办法对数组进行分组
那么我们知道a^ b^ c^ d^ a^ c = b^d我们对数组元素逐个异或之后得到的是两个只出现一次的数字异或的结果
我们举例来看

图中经过异或之后留下了1 和 6
1 和 6 的比特位最低为不一样，这个就是我们作为分组的依据

我们先对数组逐元素异或 然后找到异或结果中比特位为1的一位，这一位标识两个数在这一位上不一样 我们可以依据这个特点来分离数字

最后对两组数据分别异或就可以得到结果
代码如下

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int ret = 0;
        //得到两个只出现一次的数字的异或结果
        for(int num : nums)
        {
            ret ^= num;
        }
        //寻找两个数字不一样的位置
        int div = 1;
        while(ret)
        {
            if(ret & div)
            {
                break;
            }
            div <<= 1;
        }
        //进行分组
        vector<int> result;
        int a = 0, b = 0;
        for(int i  = 0; i  < nums.size(); ++i)
        {
            if(div & nums[i])
                a ^= nums[i];
            else
                b ^= nums[i];
        }
        result.push_back(a);
        result.push_back(b);
        return result;
    }
};

相似题目：
只出现一次的数字
数组中数字出现的次数 II

最后

以上就是满意小霸王为你收集整理的力扣leetcode剑指 Offer 56 - I. 数组中数字出现的次数C++的全部内容，希望文章能够帮你解决力扣leetcode剑指 Offer 56 - I. 数组中数字出现的次数C++所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。