Question
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?
*/
Algorithm
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.
Code
Java

public class Single_Number_III { public static void main(String[] args) { int a = 7; int b = a & a; System.out.println(Integer.toBinaryString(a)); // 111 // to negative, flip bits, and then +1 System.out.println(Integer.toBinaryString(a)); //32 bits: 11111111111111111111111111111001 System.out.println(Integer.toBinaryString(b)); } public class Solution { public int[] singleNumber(int[] nums) { if (nums == null  nums.length == 0) { return new int[]{}; } // Pass 1 : // Get the XOR of the two numbers we need to find int diff = 0; for (int num : nums) { diff ^= num; } diff &= diff; // Pass 2 : diff will distinguish two wanted numbers 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; } } }

// OJ: https://leetcode.com/problems/singlenumberiii/ // Time: O(N) // Space: O(1) class Solution { public: vector<int> singleNumber(vector<int>& A) { int x = 0; for (int n : A) x ^= n; int lb = x & (unsigned)x, a = 0; for (int n : A) { if (n & lb) a ^= n; } return {a, x ^ a}; } };

class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: List[int] """ xor = 0 for num in nums: xor ^= num xor = xor & xor a, b = 0, 0 for num in nums: if num & xor: a ^= num else: b ^= num return a, b