Day260: the number III that appears only once

problem ：

Given an array of integers nums, There are exactly two elements that only appear once , All the other elements appear twice . Find the two elements that only appear once . You can press In any order Return to the answer .

Advanced ： Your algorithm should have linear time complexity . Can you just use constant space complexity to achieve ？

Example 1：

Input ：nums = [1,2,1,3,2,5]
Output ：[3,5] explain ：[5, 3] It's also a valid answer .

Example 2：
Input ：nums = [-1,0]
Output ：[-1,0]

Example 3：
Input ：nums = [0,1]
Output ：[1,0]

source ： Power button （LeetCode）

Answer key

Train of thought ： Hashtable

1. Use the hash table to store the number of all elements in the integer array

2. The extracted number is 1 The elements of

class Solution {
    
    public int[] singleNumber(int[] nums) {
    
        Map<Integer, Integer> nums_count = new HashMap<>(); 
        for(int i : nums)
            nums_count.put(i,nums_count.getOrDefault(i,0)+1);
        int[] a = new int[2];
        int idx = 0;
        for(int i : nums){
    
            if(nums_count.get(i)==1)
                a[idx++] = i;
        }
        return a;
    }
}

Train of thought two ： Exclusive or

It is known that ：0 The result of exclusive or with an integer is the integer itself , The XOR result of two identical numbers is 0.

1. Loop exclusive or to the integer array element , Get the XOR result that only two elements appear once sum;
2. Optional sum Binary numbers are 1 Number of digits k,sum In Chinese, it means 1 Indicates that the value of the bit on this bit where the element only appears once is different , To distinguish two elements that only appear once ;
3. Pass the first k Different bits , Divide the array elements into two parts （ Each section contains only one single element ）, Redo XOR operation , Get two elements that only appear once a[0],a[1].

class Solution {
    
    public int[] singleNumber(int[] nums) {
    
        int sum = 0;
        for(int i : nums) sum ^= i;
        int k = -1;
        for(int i = Integer.toBinaryString(sum).length(); i>0; i--){
    
            if(((sum >> i) & 1) == 1) k = i;
        }
        int[] a = new int[2];
        for(int i : nums){
    
            if((( i >> k ) & 1) ==1) a[0] ^= i;
            else a[1] ^= i;
        }
        return a;
    }
}