“This is the first day of my participation in the Gwen Challenge in November. See details of the event: The last Gwen Challenge in 2021”.

This is a question of the day from LeetCode 2021-10-30: “260. Number III that only happens once”

1. Topic description

Given an integer array nums, exactly two elements appear only once, and all the rest appear twice. Find the two elements that appear only once. You can return the answers in any order.

Your algorithm should have linear time complexity. Can you do this using just constant space complexity?

Example 1:

Input: nums = [1,2,1,3,2,5] output: [3,5] explanation: [5, 3] are also valid answers.Copy the code

Example 2:

Input: nums = [-1,0] Output: [-1,0]Copy the code

Example 3:

Input: nums = [0,1] output: [1,0]Copy the code

2. Answer

This problem is similar to 136.

Xor operation:

  1. 0andAny number ofExclusive or =Any number itself
  2. Any number ofandTheir ownExclusive or =0
  3. Xor satisfies the commutative and associative laws

So if you know the above three, you can solve the problem.

The general idea is to divide numS numbers into two groups according to certain rules. The same numbers are bound to be divided into one group. The key is that two different numbers must be divided into different groups. Xor for each group, the result is two different numbers in the original array, as follows:

  • Start at 0 and xor with all the numbers in the array to get the resulttemp
  • tempEquivalent to two different numbers in an arrayXor result
  • Looking fortempIn order to1The lowest bit ofk. For example,,2,1,3,2,5 [1],temp=6, that is,110.110For the1The lowest bit of is the first bit, thenk=10
  • tempfor110, it is011and101The xOR result is1The lowest digit of theta represents two different numbers, different in this one. So let’s have two different numbers, alpha and betakforwithOperation, you can separate
  • Grouping,011 & 10.101 & 10, two different numbers can be divided into two groups, the rest of the same numbers will be grouped in the same group
  • Each group performs xOR operations separately to get two answers
const singleNumber = nums= > {
    let temp = 0;
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        temp = temp ^ nums[i];
    }
    // Temp is the result of two different xor values
    // Find k, which is a binary number with temp least significant 1 and other bits 0
    let k = 1;
    while ((temp & k) === 0) k = k << 1;

    let [num1, num2] = [0.0];
    for (let i = 0; i < len; i++) {
        // Grouping, the purpose is to separate two different numbers
        if (nums[i] & k) {
            num1 = num1 ^ nums[i];
        } else{ num2 = num2 ^ nums[i]; }}return [num1, num2];
};
Copy the code