LeetCode_ Bit operation_ Medium_ 260. Number III that appears only once

1. subject

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 do it 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]

Tips ：
2 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Except for two integers that appear only once ,nums The other numbers in appear twice

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/single-number-iii

2. Ideas

（1） Hashtable
If you use extra space , It is easy to think of using hash table , First add all the elements in the array to hashMap in （ key / Value is element value / The number of occurrences of this element ）, Then find the element that only appears once in the hash table and return it .

（2） An operation
Train of thought reference The LeetCode User questions .

The following is an example to illustrate the process of this method ：
① Hypothetical array nums = {1, 2, 1, 3, 2, 5}, The binary numbers corresponding to the elements are ：
00…001
00…010
00…001
00…011
00…010
00…101
XOR them , The result is zero xorSum = 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = 3 ^ 5 = (00…011 ^ 00…101) = 00…110.

② Take it now xorSum In binary representation 1 a k, for example k = 2, It means Array nums The binary representation of the element that appears only once in k Different bits , This corresponds to 00…011 and 00…101.

③ Yes nums Traversal , Right. k The bits are 0 and 1 The elements of are different or and , In this way, the two answers will inevitably be divided into different groups , The specific process is as follows ：

 Array  nums  Binary representation in  2  Position as  0  The elements of  1, 2, 1, 3, 2
 Array  nums  Binary representation in  2  Position as  1  The elements of  5
1 ^ 2 ^ 1 ^ 3 ^ 2 = 3
5 = 5
 Because for any number  a,a ^ 0 = a, So for the convenience of saving results , The length can be defined as  2  The result array of  res, Their initial values are  0, that 
res[0] = res[0] ^ 1 ^ 2 ^ 1 ^ 3 ^ 2 = 3
res[1] = res[1] ^ 5 = 5
 This finds the array  nums  Two elements that appear only once in ！

Similar topics ：
LeetCode_ An operation _ Simple _136. A number that appears only once
LeetCode_ An operation _ secondary _137. A number that appears only once II

3. Code implementation （Java）

// Ideas 1———— Hashtable 
class Solution {
    
    public int[] singleNumber(int[] nums) {
    
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
    
            hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
        }
        int cnt = 0;
        int[] res = new int[2];
        for (Integer num : hashMap.keySet()) {
    
            if (hashMap.get(num) == 1) {
    
                res[cnt++] = num;
            }
        }
        return res;
    }
}

// Ideas 2———— An operation 
class Solution {
    
    public int[] singleNumber(int[] nums) {
    
        int[] res = new int[2];
        /* xorSum  It's an array  nums  The result of XOR operation on all elements in   Because except for two integers that only appear once , Array  nums  The other numbers in appear twice , And the XOR of two identical numbers   The result of the operation is  0, therefore  xorSum  Is the XOR value of two integers that occur only once  */
        int xorSum = 0;
        for (int num : nums) {
    
            xorSum ^= num;
        }
        int k = -1;
        for (int i = 31; i >= 0 && k == -1; i--) {
    
            if (((xorSum >> i) & 1) == 1) {
    
                k = i;
            }
        }
        for (int num : nums) {
    
            if (((num >> k) & 1) == 0) {
    
                res[0] ^= num;
            } else {
    
                res[1] ^= num;
            }
        }
        return res;
    }
}