LeetCode_ Bit operation_ Medium_ 137. Number II that appears only once

1. subject

Give you an array of integers nums , Except that an element appears only once , Each of the other elements occurs exactly three times . Please find and return the element that only appears once .

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

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

Tips ：
1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
nums in , Except that an element appears only once , Each of the other elements occurs exactly three times

Advanced ： Your algorithm should have linear time complexity . Can you do this without using extra space ？

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

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） Hash set
First use the set hashSet To store arrays nums All elements that appear in , And calculate the array nums The sum of all elements in . And because of the non repetition of set elements , So assemble hashSet Three times the sum of all the elements in is the array nums The sum of elements in the case where each element occurs three times . It can be seen from the title , Array nums Only one element appears once in , The other elements appear three times , therefore The element value that appears only once = (nums The sum of all non repeating elements in * 3 - nums The sum of all the elements of ) / 2. However, attention should be paid to when writing int Integer overflow problem ！

（3） An operation
The length used is 32 Array of cnt To record the array nums Every bit of the binary bit corresponding to all elements in 1 The total number of times , And then the array cnt The value of each element in mod 3 operation , The result of splicing is an array nums Elements that appear only once in . For ease of understanding , Take the following example to introduce ：

(1)  Hypothetical array  nums = {
    2, 2, 3, 2, 5, 5, 5}, The binary numbers corresponding to the elements are ：
00...010
00...010
00...011
00...010
00...101
00...101
00...101

(2)  It can be seen from the calculation  cnt = {
    0, 0, ..., 3, 4, 4}, With  cnt[31] = 4  For example , It said  2, 2, 3, 2, 5, 5, 5  The lowest bit of the corresponding binary number has  4  individual  1

(3)  Because of arrays  nums  in , Except that an element appears only once , Each of the other elements occurs exactly three times , Then it shows that every bit of the binary number corresponding to the element that appears three times also appears  3  Time ,
 This is reflected in the array  cnt  The situation in is  cnt[i] == k * 3 + 1/0, among  k  Indicates when the binary bit is  1  The number of elements that appear three times , So for arrays  cnt  Every element in 
 Conduct  mod 3  After operation, we get  {
    0, 0, ..., 0, 1, 1}, It is clear that it will  0, 0, ..., 1, 1  The number obtained after splicing is the binary number corresponding to the element that appears only once , namely  Nums  Medium  3.

in addition , The time complexity of the algorithm is O(n), The space complexity is O(1).

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

3. Code implementation （Java）

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

// Ideas 2———— Hash set 
class Solution {
    
    public int singleNumber(int[] nums) {
    
        HashSet<Integer> hashSet = new HashSet<>();
        long sum = 0;
        for (int num : nums) {
    
            hashSet.add(num);
            // Compute arrays  nums  The sum of all the elements in 
            sum += (long)num;
        }
        long setSum = 0;
        for (Integer num : hashSet) {
    
            // Compute arrays  nums  The sum of all non repeating elements in 
            setSum += (long)num;
        }
        return (int)((3 * setSum - sum) / 2);
    }
}

// Ideas 3———— An operation 
class Solution {
    
    public static int singleNumber(int[] nums) {
    
        int res = 0;
        // Record how many times each digit of all values appears  1
        int[] cnt = new int[32];
        for (int num : nums) {
    
            for (int i = 0; i < 32; i++) {
    
                /* num >> i: num  All binary values of the corresponding binary number are shifted to the right  i  position  (num >> i) & 1:  obtain  num >> i  The lowest bit of a binary number  */
                if (((num >> i) & 1) == 1) {
    
                    cnt[i]++;
                }
            }
        }
        for (int i = 0; i < 32; i++) {
    
            if ((cnt[i] % 3 & 1) == 1) {
    
            	// Joining together the results 
                res += (1 << i);
            }
        }
        return res;
    }
}