Formatted question description: https://leetcode.ca/all/260.html
/** 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. Example: Input: [1,2,1,3,2,5] Output: [3,5] Note: The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity? */
This question is actually a very clever use of the ·Single Number· solution, because that solution can accurately find a number that appears only once, but the premise is that other numbers must appear twice.
And this question has two numbers that only appear once, so if we can find a way to divide the original array into two small arrays, the two different numbers are in the two small arrays, so that the Single Number solution is called separately You can get the answer.
So how to achieve it, first we XOR all the original array, then we will get a number, this number is the result of the XOR of two different numbers, we take out any one of the bits that is ‘1’, For the sake of convenience, we use ·a &= -a· to take out the bit whose rightmost end is ‘1’, specifically how to operate this.
Take the example in the title, if we “exclusive OR” all of them, we know that the “exclusive OR” of the same two numbers is 0, then the two 1, and the two 2 are cancelled out, and there is nothing left 3 and 5’exclusive OR’, which is the binary 11 and 101’exclusive OR’, get 110.
Then we perform
a &= -a operation. First change the negative number. In binary, the negative number is in the form of complement, and the complement is the complement +1, then the complement of 110 is 11…1001, then after adding 1, it is 11…1010, and then 110 And, get 10, which is the diff variable in the code.
With this diff, the original array can be divided into two arrays. Why, if two identical numbers are “XOR”, each of them will be 0, and different numbers will be “XOR”, there must be different corresponding bits, one 0 and one 1, so “XOR” ‘ it’s 1.
For example, the binary 11 and 101 of 3 and 5, if you look from low to high, the first difference is the second digit. Then we use the second digit to AND each number in the array. Depending on the result, it must be possible to distinguish 3 and 5, and because the other numbers appear in pairs, they are also paired. In the end, they will be XORed into 0, and 3 and 5 will not be affected. XOR the numbers in the two groups separately to get the final result.