跳转至

260.Single Number III

Tags: Medium Bit Manipulation

Links: https://leetcode.com/problems/single-number-iii/

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> result(2, 0);
        int sum = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());

        int flag = sum & (~(sum - 1));

        for (auto e : nums){
            if ((e & flag) == 0) result[0] ^= e;
            else result[1] ^= e;
        }

        return result;
    }
};
  1. 数组中所有数字做异或运算，因为有两个元素只出现一次，所以最后的异或运算结果sum 为两个单独元素x，y的异或结果。因为相同数字异或运算结果为0。

我们要得到x，y的结果，就是要利用sum把x，y分出来。

  1. 我们把数组nums分为两组，其中x在一组，y在另一组。那么按照什么来分组呢？

我们知道数组所有元素异或运算（也就是x，y的异或运算）sum的结果一定不为0，因为x≠y，那么x和y的二进制表示中肯定有一或多位不相等，即肯定存在x中的某一位值为 1 ， y中相同位的值为 0 。我们依据x和y中某一位值不一样将数组分为两组：

分组一包含x，也就是某特定位为1（0）的所有元素，分组二包含y，也就是某特定位为0（1）的所有元素。

  1. 那么接下来，怎样按照上述方法去判断数组中某位的值是0是1呢？

可以用与&运算。我们引入一个flag值，flag表示的是x，y的二进制表示中，值不同的一位，将这一位取值为1，其它所有位取值为0（如果还存在其它取值不同的位，也置为0）。这里我们确定flag值的方法 ：  flag = sum & (~(sum - 1));

举个例子，比如 x = 5，y = 3： 

首先转换二进制 x = 101 y = 11     ——>    异或运算  sum = x ^ y = 110    ——>    flag取值 flag = 10 （010）

  1. 好找到了flag然后可以用与&运算了，x，y中肯定有一个数字同flag做与&运算时取值为0。为啥，因为flag为0的位，无论同1还是0做与运算都位0，那么flag为1的位只有一位，而这位是根据x，y不同位确定的位数，也就是说x，y同flag为1位相同的位数，一个是0，另一个是1，是0的那个数做与运算当然结果为0了。 其它数也根据是根据这个道理，进行了分组。

  2. 最后将分组一内所有的元素做异或运算，得出x，将分组二内所有元素做异或运算，得出y。为啥，因为啊分组一（二）中的数，除去x和y以外，都是相同的数字啦，相同的数字做异或，得0呀。