Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Topic describes

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.

Advanced: 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.
Solution: bit operation

Xor operation features:

  • 0 and any number xor = any number itself
  • Any number and itself xor =0
  • Xor satisfies the commutative and associative laws

Analysis:

  • The numS number is divided into two groups according to certain rules. The same number must 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, resulting in temp
    • Temp is equivalent to the xor result of two different numbers in an array
    • Find the lowest bit k in temp, which is 1. For example, if [1,2,1,3,2,5], temp=6, that is, 110,110 is the lowest bit of 1 is the first bit, then k=10
    • Temp is 110, which is the xor of 011 and 101. The least significant value of 1 represents two different numbers that differ in this digit. So if you take two different numbers, and k, and operate with them, you can separate them
    • Grouping, 011&10, 101&10, can put two different numbers in two groups, the rest of the same numbers will definitely 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

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤