thinking

According to the meaning of the question, if the space complexity is required to be O(1), the hash table cannot be used. This problem examines bit operations.

Tips: if only one number in the array appears only once, XOR each number from beginning to end, the final result is the number that appears only once. Reason: the XOR operation satisfies the commutative law, and the numbers that appear twice in pairs are all offset in the XOR.  

Then for this problem, two numbers in the array appear only once. If you can divide the array into two parts, and only one number in both parts appears only once, you can solve this problem. At this point, we XOR each number from beginning to end, and the final result is the XOR result of two numbers that only appear once. Since the two numbers are different, at least one bit in the binary representation of the resulting number is 1. We record the position of the first 1 in the result from right to left as the nth bit, because this is the XOR result of two numbers that only appear once, so the numbers of these two numbers in the nth bit must be 1 and 0

Now we divide the number in the original array into two parts based on whether the nth bit is 1. The nth bit of each number in the first sub array is 1, and the nth bit of each number in the second sub array is 0 Because any bit of two identical numbers is the same, the numbers that appear twice must be assigned to the same subarray.

Finally, XOR the two sub arrays from beginning to end to get these two numbers.

solution

//num1,num2 Each is an array of length 1. out parameter 
//take num1[0],num2[0]Set to return results
import java.util.*;
public class Solution {
    // use HashMap
    /*public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if (array == null || array.length < 2)
            return;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int num : array){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        boolean flag = true;
        for (int key : map.keySet()){
            if (map.get(key) == 1){
                if (flag){
                    num1[0] = key;
                    flag = false;
                }else{
                    num2[0] = key;
                }
            }
        }
    }*/
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if (array == null || array.length < 2)
            return;
        int ans = 0;
        // The first loop finds the XOR result of the two numbers that appear only once
        for (int num : array)
            ans ^= num;
        // Find the number corresponding to the first position that is not 0 from right to left and use it to divide the array.
        int indexOf1 = 1;
        while ((ans & indexOf1) == 0)
            indexOf1 <<= 1;
        num1[0] = 0;
        num2[0] = 0;
        for (int x : array){
            if ((x & indexOf1) == 0){
                num1[0] ^= x;
            }else{
                num2[0] ^= x;
            }
        }
    }
}

harvest

When a number appears twice (or even times), XOR ^ can be used to eliminate it.

reference resources: