Topic:

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.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

Source: LeetCode link: leetcode-cn.com/problems/si… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Concluding thinking

  1. When an array has only one number that appears only once

Xor: same bit xor or result is 0, different bit xor result is 1

0 to the 1 is 1. 1 to the 1 is 0Copy the code

If an array [1,1,2,2,3,3,4] occurs twice and only one occurs once, then xor each digit in the array. The result of xor is 0. Finally, 0 xor 4 is 4.

  1. When there are two numbers in the array that occur only once

In their case, there are two numbers a and B that occur only once, so the xOR of the entire array is the xOR of those two numbers, a to the b. For example, the xor of [1,2,1,3,2,5] is 3^5. The xor of the entire array is 0011^0101=0110.

Take the xor result of the entire array and find the first bit that is 1 from right to left. This bit will divide the entire array into two groups. 3 and 5 will be divided into different groups, thus transforming the problem into the situation described in the two 1’s summary. Xor the two groups separately yields two numbers that appear only once.

The specific algorithm

public int[] singleNumber(int[] nums) {
    // Record the xOR result of group A
    int a = 0;
    // Record the xOR result of group B
    int b = 0;
    // Record xOR results
    int xor = 0;

    // Get the xOR of the entire array. The same number is 0
    for (int i = 0; i < nums.length; i++) {
        xor ^= nums[i];
    }

    // Find the first 1 bit for xor from right to left
    int div = 1;
    while ((xor & div) == 0) {
        div = div << 1;
    }

    // Iterate over the array, using div to split the array into two groups, one or the other, to get two values that occur only once
    for (int i = 0; i < nums.length; i++) {
        if ((div & nums[i]) == 0) {
            a = a ^ nums[i];
        } else{ b = b ^ nums[i]; }}// return a and b
    return new int[]{a, b};
}
Copy the code