LeetCode题目改编——只出现一次的数字IV
2019-05-04

起源

受LeetCode系列题目启发

只出现一次的数字I

只出现一次的数字II

只出现一次的数字III

已提交贡献（然而几个月了都是Pending，发到博客来吧~

题目

给定一个正整数数组 nums，其中恰好有三个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那三个元素。

示例 :

输入: [1, 6, 2, 4, 1, 3, 2, 5, 6]
输出: [3, 4, 5]

注意：

  1. 结果输出的顺序并不重要，对于上面的例子，可以是 3, 4, 5 的任意排列。
  2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

解题

这道题比 “只出现一次的数字III” 多了一个只出现一个的数字，我们只要找到三个只出现一个的数字中一个，加入数组中，再使用 “只出现一次的数字III” 寻找两个只出现一次的数字即可

首先记 LSB(x) = x & (-x)，表示取x的二进制最低的位1，其他位均置为0，如LSB(100110b) = 000010b ，若x > 0，则 LSB(x) > 0

设三个只出现一次的正整数为 a, b, c , 设 n = a ^ b ^ c（对数组中所有数进行异或可得n），由异或的交换律和结合律有 (n ^ a) ^ (n ^ b) ^ (n ^ c) = 0

显然也有 LSB(n ^ a) ^ LSB(n ^ b) ^ LSB(n ^ c) != 0， 即至少有一个二进制位是1，因为任意两个LSB(·)异或运算结果为0或者有两个二进制位1

设 k为LSB(LSB(n ^ a) ^ LSB(n ^ b) ^ LSB(n ^ c)) 的位1所在位置，即k是 LSB(n ^ a)， LSB(n ^ b)， LSB(n ^ c)为三者中最小的最低位1的位置，则 (n ^ a)， (n ^ b)， (n ^ c)三者在第 k 位上只有3种可能，有3个1，2个1或1个1。

如果有3个1或者1个1，则第 k位异或结果为1，与 (n ^ a) ^ (n ^ b) ^ (n ^ c) = 0矛盾

因此(n ^ a)， (n ^ b)， (n ^ c)三者在第 k 位上只能有2个1，我们现在要寻找的三个数种的第一个数就是第 k 位上是0的那个数，不妨设为c

为此，我们初始化n = 0遍历数组，依次计算n ^= arr[i]，得到n = a ^ b ^ c，

初始化lsb = 0，再次遍历数组，依次计算lsb ^= LSB(n ^ arr[i])，结果得到的 lsb 就是LSB(n ^ c) ，因为对于那些出现两次的数x，LSB(n ^ x) ^ LSB(n ^ x) = 0，而对于n ^ a和n ^ b，它们在第k位（也是它们的最低位的1）都是1，因此，LSB(n ^ a) ^ LSB(n ^ b) = 0

初始化c = 0，再次遍历数组，如果LSB(n ^ arr[i]) == lsb，计算c ^= arr[i] ，最后结果c就是我们要寻找的数，因为LSB(n ^ arr[i]) == lsb筛选出的arr[i]最低位1的位置和lsb相同（也就是和c相同），这些数的异或结果只会留下c，出现两次的数都抵消了

C++代码

#include <iostream>
#include <vector>
using namespace std;
int LSB(int num){ //取最低位的1，其他位均置为0
    return num & (-num);
}
vector<int> Two(vector<int> arr){ //寻找数组中两个只出现一次的数（其他数都出现两次）
    int a_xor_b = 0, a = 0, b = 0, lsb = 0;
    for (int i = 0; i < arr.size(); i++)
        a_xor_b ^= arr[i];
    lsb = LSB(a_xor_b);
    for (int i = 0; i < arr.size(); i++)
        if(arr[i] & lsb)
            a ^= arr[i];
    b = a_xor_b ^ a;
    return vector<int>{a, b};
}
int OneOfThree(vector<int> arr){ //寻找数组中三个只出现一次的数中的一个（其他数都出现两次）
    int a_xor_b_xor_c = 0, c = 0, lsb = 0;
    for (int i = 0; i < arr.size(); i++)
        a_xor_b_xor_c ^= arr[i];
    for (int i = 0; i < arr.size(); i++)
        lsb ^= LSB(a_xor_b_xor_c ^ arr[i]);
    lsb = LSB(lsb);
    for (int i = 0; i < arr.size(); i++)
        if (LSB(a_xor_b_xor_c ^ arr[i]) == lsb)
            c ^= arr[i];
    return c;
}
vector<int> Three(vector<int> arr){ //寻找数组中三个只出现一次的数（其他数都出现两次）
    int c = OneOfThree(arr);
    arr.push_back(c);
    vector<int> res = Two(arr);
    res.push_back(c);
    return res;
}
int main(){
    vector<int> arr = {1, 6, 2, 4, 1, 3, 2, 5, 6};
    vector<int> res = Three(arr);
    for(int i = 0; i < 3; i++)
        cout << res[i] << " ";
    return 0;
}

参考

http://lijinma.com/blog/2014/05/29/amazing-xor/

http://www.360doc.com/content/14/0728/12/14505022_397625773.shtml

搜索
背景设置