欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数组中只出现一次的数字---剑指offer

程序员文章站 2022-07-14 20:22:31
...

数组中只出现一次的数字

C++,位运算,按位异或和按位与。

首先就是要知道,一个数a和初始为0的数b一次异或(b = a ^ b),会得到b = a,两次异或,则b = 0。所以如果一个序列中,只有一个元素a出现次数为奇数,其他序列出现次数为偶数,将数b = 0与序列中所有值进行异或运算,则最终b = a。

这道题中给的序列中有两个出现了一次的元素a、b,其他都出现了两次。我们可以把这个序列分成两个子序列,每个子序列中包含一个出现一次的元素a和,其他都是出现了2次,这样分别异或运算就能得到答案了。

如何给序列分割呢?

  • 首先定义一个变量a_b = 0,与序列中所有元素都进行异或^运算;
  • 最后得到的a_b一定是等于a ^ b;
  • 然后再找到a_b的二进制中第一个为1的位,假设这个位为i,这个位对于整个序列具有如下特点:
    • 如果a的i位为1,则b的i为一定为0,反之也成立,因为这个1是a和b异或的结果;
    • 相同的数的i位一定是相同的;
  • 基于上述特点,可以用按位与将序列分成两个子序列,且这两个子序列中一定是符合“只有一个元素出现了1次,其他元素都出现了2次”的特征。
class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int a_b = 0;
        for (int &it : data) a_b ^= it;
        int i = 1;
        for (; !(i & a_b); i <<= 1) ;
        vector<int> v1, v2;
        for (int &it : data) {
            if (i & it)
                v1.push_back(it);
            else
                v2.push_back(it);
        }
        a_b = 0;
        for (int &it : v1) a_b ^= it;
        *num1 = a_b;
        a_b = 0;
        for (int &it : v2) a_b ^= it;
        *num2 = a_b;
    }
};
相关标签: 剑指offer 刷题