LeetCode 260 - Single Number III

Related: LeetCode 137 - Single Number II
LIKE CODING: LeetCode [260] 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.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [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?

X.
http://www.cnblogs.com/grandyang/p/4741122.html
这道题其实是很巧妙的利用了 Single Number 的解法，因为那道解法是可以准确的找出只出现了一次的数字，但前提是其他数字必须出现两次才行。而这题有两个数字都只出现了一次，那么我们如果能想办法把原数组分为两个小数组，不相同的两个数字分别在两个小数组中，这样分别调用 Single Number 的解法就可以得到答案。那么如何实现呢，首先我们先把原数组全部异或起来，那么我们会得到一个数字，这个数字是两个不相同的数字异或的结果，我们取出其中任意一位为‘1’的位，为了方便起见，我们用 a &= -a 来取出最右端为‘1’的位，具体来说下这个是如何操作的吧。就拿题目中的例子来说，如果我们将其全部亦或起来，我们知道相同的两个数亦或的话为0，那么两个1，两个2，都抵消了，就剩3和5亦或起来，那么就是二进制的11和101亦或，得到110。然后我们进行 a &= -a 操作。首先变负数吧，在二进制中负数采用补码的形式，而补码就是反码+1，那么110的反码是 11...1001，那么加1后是 11...1010，然后和 110 相与，得到了10，就是代码中的diff变量。得到了这个diff，就可以将原数组分为两个数组了。为啥呢，我们想阿，如果两个相同的数字亦或，每位都会是0，而不同的数字亦或，一定会有对应位不同，一个0一个1，这样亦或是1。比如3和5的二进制11和101，如果从低往高看，最开始产生不同的就是第二位，那么我们用第二位来和数组中每个数字相与，根据结果的不同，一定可以把3和5区分开来，而其他的数字由于是成对出现，所以区分开来也是成对的，最终都会亦或成0，不会3和5产生影响。分别将两个小组中的数字都异或起来，就可以得到最终结果了
https://leetcode.com/problems/single-number-iii/discuss/68900/Accepted-C%2B%2BJava-O(n)-time-O(1)-space-Easy-Solution-with-Detail-Explanations

Once again, we need to use XOR to solve this problem. But this time, we need to do it in two passes:

• In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit (that is, the bit with value '1') in the XOR result. Find
  out an arbitrary set bit (for example, the rightmost set bit).
• In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the aforementinoed bit unset. Two different numbers we need to find must fall into thte two distrinct groups. XOR numbers in each group, we can find a number in either group

    public int[] singleNumber(int[] nums) {
        // Pass 1 : 
        // Get the XOR of the two numbers we need to find
        int diff = 0;
        for (int num : nums) {
            diff ^= num;
        }
        // Get its last set bit
        diff &= -diff;
        
        // Pass 2 :
        int[] rets = {0, 0}; // this array stores the two numbers we will return
        for (int num : nums)
        {
            if ((num & diff) == 0) // the bit is not set
            {
                rets[0] ^= num;
            }
            else // the bit is set
            {
                rets[1] ^= num;
            }
        }
        return rets;
    }
}

https://leetcode.com/problems/single-number-iii/discuss/69006/My-Java-solution-adapted-from-the-commonest-solution-here
Instead of using the right-most "1" of diff, I used the left-most "1" to divide groups. This should also do the trick.

public class Solution {
public int[] singleNumber(int[] nums) {
    int diff = 0;
    for(int num: nums){
        diff^=num;
    }
    diff = Integer.highestOneBit(diff);
    
    int[] result = new int[2];
    Arrays.fill(result,0);
    for(int num: nums){
        if((diff & num) == 0){
            result[0] ^= num;
        }
        else{
            result[1] ^= num;
        }
    }
    return result;
}

https://leetcode.com/problems/single-number-iii/discuss/68901/Sharing-explanation-of-the-solution

The two numbers that appear only once must differ at some bit, this is how we can distinguish between them. Otherwise, they will be one of the duplicate numbers.

One important point is that by XORing all the numbers, we actually get the XOR of the two target numbers (because XORing two duplicate numbers always results in 0). Consider the XOR result of the two target numbers; if some bit of the XOR result is 1, it means that the two target numbers differ at that location.

Let’s say the at the ith bit, the two desired numbers differ from each other. which means one number has bit i equaling: 0, the other number has bit i equaling 1.

Thus, all the numbers can be partitioned into two groups according to their bits at location i.
the first group consists of all numbers whose bits at i is 0.
the second group consists of all numbers whose bits at i is 1.

Notice that, if a duplicate number has bit i as 0, then, two copies of it will belong to the first group. Similarly, if a duplicate number has bit i as 1, then, two copies of it will belong to the second group.

by XoRing all numbers in the first group, we can get the first number.
by XoRing all numbers in the second group, we can get the second number

http://www.chenguanghe.com/single-number-iii/
思路是这样的: 首先用一个变量diff, 对每个数做xor, 这样得到的diff里面只有这两个数字中bit不同的位代表的数字,diff是一定不为0的, 因为这两个数不同, 不然所有数都出现两次了, 其他的数字因为出现两次, 都被xor删除了, 剩下的两个数字的不同位的代表的数. diff虽然表示了两个数中不同位, 但是它不能用来直接计算, 因为如果用它判断这两个数, 不能确保判断出两个数的位是留下的位. 所以这里我们要取diff中的最右边的为1的位. 这里用的方法是:
int rightBit = diff & -diff;

这个1的意义是, 我们需要找的两个数可以通过这个1来区别. 所以我们通过这个1,可以把数组分成两组, 每组都包含一个我们要找的数, 因为其他数都是出现两次, 所以留下的就是最后我们要找的答案

    public int[] singleNumber(int[] nums) {

        if (nums.length == 0 || nums == null)

            return null;

        int diff = 0;

        for(int i : nums)

            diff ^= i;

        int rightBit = diff & -diff;

        int[] result = new int[]{0,0};

        for(int i : nums){

            if((i & rightBit) == 0)

                result[0] ^= i;

            else

                result[1] ^= i;

        }

        return result;

    }

https://leetcode.com/discuss/52351/accepted-java-space-easy-solution-with-detail-explanations

Once again, we need to use XOR to solve this problem. But this time, we need to do it in two passes:

• In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit in the XOR result. Find out the bit.
• In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the aforementinoed bit unset. Two different numbers we need to find must fall into thte two distrinct groups. XOR numbers in each group, we can find a number in either group.

public int[] singleNumber(int[] nums) { // Pass 1 : // Get the XOR of the two numbers we need to find int diff = 0; for (int num : nums) { diff ^= num; } // Get its last set bit diff &= -diff; // Pass 2 : int[] rets = {0, 0}; // this array stores the two numbers we will return for (int num : nums) { if ((num & diff) == 0) // the bit is not set { rets[0] ^= num; } else // the bit is set { rets[1] ^= num; } } return rets; }

    vector<int> singleNumber(vector<int>& nums) {

        int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());

        diff &= -diff;

        vector<int> ret(2);

        for(int n:nums){

            if(diff & n){

                ret[0] ^= n;

            }else{

                ret[1] ^= n;

            }

        }

        return ret;

    }

http://fisherlei.blogspot.com/2015/10/leetcode-single-number-iii-solution.html

这题有两个未知数，直接做异或肯定是不行的，那么如何通过一些变换把这道题分解开，使得可以应用Single Number的解法来做，才是这个题目有意思的地方。

首先，对于数组A, 假设存在b，c两个数字，在数组中只出现了一次，那么对于整个数组进行异或操作的话，

^[A]   =  b^c ,  因为其他的数因为出现了两次，异或的过程中就被清零了。

但是仅仅通过最后异或出来的值，是没办法求出b和c的值的，但是足以帮我们把b和c划分到不同的子数组中去。

一个整数有32位bit，对于b和c，除非两者是相同的数，否则一定存在第K位bit，两者是不同的。看下面的例子，

当找到这个K以后，就可以按照第K位bit是否等于1，将A数组划分成两个子数组，而这两个子数组分别包含了b和c，那么剩下的就只需要把single number的算法直接应用到这两个子数组上，就可以得到b和c了

3:    vector<int> singleNumber(vector<int>& nums) {  
4:      int length = nums.size();  
5:      // get the xor result of the array, b ^ c  
6:      int xor_result = 0;  
7:      for(int i =0; i< length; i++) {  
8:        xor_result ^= nums[i];  
9:      }  
10:      // get the K of first bit, which equals 1  
11:      int first_one_index = 0;  
12:      for(first_one_index =0; first_one_index< 32; first_one_index++) {  
13:        if((xor_result>>first_one_index) & 1 == 1) {  
14:          break;  
15:        }  
16:      }  
17:      // use k to split the array into two part  
18:      // xor the sub array, if the element's Kth bit also equals 1, b  
19:      int xor_twice = 0;  
20:      for(int i =0; i< length; i++) {  
21:        if((nums[i]>>first_one_index) & 1 == 1) {  
22:          xor_twice ^= nums[i];  
23:        }  
24:      }  
25:      // with b, easy to get c by math  
26:      vector<int> result = {xor_twice, xor_result ^ xor_twice };   //\\   
27:      return result;  
28:    }  

https://www.jianshu.com/p/b5e4e7870259

然后再次遍历数组，使用条件 num & mask == 0 将数字分为两组，分别取异或 s ，则可以得到 a 和 b。

    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        bit_num = 0
        for num in nums:
            bit_num ^= num
        mask = 1
        a = b = bit_num
        while (bit_num & mask == 0):
            mask = mask << 1
        for num in nums:
            if (num & mask):
                a ^= num
            else:
                b ^= num
        return [a, b]

X. https://blog.csdn.net/Cloudox_/article/details/53995027

最简单的方法就是排序后，依次检查相邻两个数是否相等，当然遇到相等的就要跳一个数字再进行检查，遇到不相等的就记录下来是结果，注意如果单个的元素排序后在最末尾，要单独处理。

这个做法排序是需要时间和空间的，并不完全符合题目的要求。

    public int[] singleNumber(int[] nums) {

        Arrays.sort(nums);

        int[] result = new int[2];

        int index = 0;

        int i = 0;

        for (; i < nums.length-1; i++) {

            if (nums[i] != nums[i+1]) {

                result[index] = nums[i];

                index ++;

            }

            else i++;

        }

        if (i < nums.length) result[index] = nums[i];

        return result;

    }