首页 > 代码库 > 剑指offer (40) 数组中只出现一次的数字

剑指offer (40) 数组中只出现一次的数字

2024-07-09 18:17:16   219人阅读

题目：一个整型数组里除了两个数字之外，其余的数字都出现了两次，求这两个只出现一次的数字

 

题解分析：

首先看到数字出现1次，出现2次，应该联想到 异或运算：

0^a = a

a^a = 0

如果数组中只有一个数字出现奇数次，其余都出现偶数次，我们就可以将这些数字全部异或，最后的结果即为所求(因为所有偶数次数字异或之后相消了)

 

但是：现在数组中有两个只出现1次的数字，我们可不可以将原数组划分为两个子数组，子数组要求只能有一个数字出现1次，其余都是偶数次

事实上是可以的，操作如下：

step1. 将原数组数字全部异或，结果记为M，因为偶数次数字全部抵消了，只剩下只出现1次的两数字异或，结果肯定不为0，因为这两个数字不同

结果M肯定不为0，那么其二进制表示中就一定存在某位为1，我们就找到M中第一个为1的位置，记为第n位

 

step2. 我们现在以 数字第n位是否为1 为标准将原数组中的数字划分为两个子数组，这两个子数组一定就是我们所希望的

因为出现偶数次的这些数，任意相同的数字的二进制表示肯定是相同的，所以肯定会被分到同一组

最后只出现1次的两个数a和b，因为异或结果第n位为1，那么a和b的第n位一定是不同的(异或是 不同为1，相同为0)

 

step3， 对两个子数组分别求出只出现1次的数字

 

int GetOnce(std::vector<int>& num){    assert(num.size() > 0);    int result = 0;    for (int i = 0; i < num.size(); ++i) {        result ^= num.at(i);    }    return result;}// 找到num从右边数起第一个是1的位unsigned int FindFirstBit1(int num){    unsigned int index = 0;    while ((num & 1) == 0 && (index < 8 * sizeof(int))) {        num >>= 1;        ++index;    }    return index;}// 判断数字num的第index位是不是1bool IsBit1(int num, unsigned int index){    num >>= index;    return num & 1;}void GetTwoOnce(std::vector<int>& num){    if (num.size() == 0) return;    int res = GetOnce(num);    unsigned int bit = FindFirstBit1(res);    int num1 = 0;    int num2 = 0;    for (int i = 0; i < num.size(); ++i) {        if (IsBit1(num.at(i), bit)) {            num1 ^= num.at(i);        } else {            num2 ^= num.at(i);        }    }    std::cout << num1 << " " << num2 << std::endl;}

 


联系
我们