The 21st layer of leetcode Langya list - numbers that only appear once

LeetCode The 21st floor of Langya list - A number that appears only once ( Binary algorithm )

subject

Title browsing

Key information extraction

• Except that an element only appears once , The others appeared three times
• 2e-31 <= nums[i] <= 2e31 - 1
• The time complexity of the algorithm should be linear

Topic information interpretation

• In the array , There are only two possible situations
  • A certain element has been thought about three times
  • A certain element is thought of once
• The value range of each element is in one int Within the scope of

Description of algorithm

Hash counting method

• There are two main types of hash counting
  • adopt HashSet Set to count , Generally, this set deals with elements that have been thought of many times
  • adopt HashMap Set to count , Generally, this collection deals with elements that only appear once
  • Obviously , What we use here is **HashMap** Set to count

Binary solution

• This method is very wonderful , Belong to us Force buckle 20 layers One of the Prepositive method

Algorithm details

Algorithmic thought

Hash counting method

• Let's go through it once nums Array , Through one HashMap To record the number of occurrences of each element
• Go over it again HashMap, Find the element that only appears once

Binary solution

analysis

1. The breakthrough of this algorithm is our Binary digit , So we first get the of each element Binary digit , And align its position
2. Aim at Elements that have appeared three times , their Binary digit It must be the same , That is, the following... Will appear on the corresponding binary bit Two cases
   1. 1 + 1 + 1 = 3 % 3 = 0
   2. 0 + 0 + 0 = 0 % 3 = 0
3. In either case it is 3 Multiple , The same reasoning goes to all elements that have appeared three times , As long as this element It has appeared three times on the corresponding binary bit %3 It must be equal to 0
4. If the final result (res = sum % 3) != 0, explain , This res It must have happened once Binary digit , Record these binary bits to get the number that has appeared once

Code implementation and Analysis

Hash counting method

class Solution {
    public int singleNumber(int[] nums) {
        var map = new HashMap<Integer,Integer>();
        var target = 0;
        for (var num : nums) {
            //  If the element doesn't exist , It is assigned as 0+1, Otherwise it is the original size +1
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        for (var res : map.entrySet()) {
            if (res.getValue() == 1) {
                target = res.getKey();
                break;
            }
        }
        return target;
    }
}

Binary solution

class Solution {
    public int singleNumber(int[] nums) {
        // target  Used to record the final results 
        var target = 0;
        //  Every element is in int Within the scope of , So there is 32 individual bit position , loop 32 Time 
        for (int i = 0; i < 32; i++) {
            //  Record the sum of each binary bit 
            var sum = 0;
            for (var num : nums) {
                //  Get the sum of each binary bit , For details, please see the analysis 1
                sum += (num >> i) & 1;
            }
            //  For details, please see the analysis 2 
            if (sum % 3 != 0) {
                target |= (1 << i);
            }
        }
        //  Return the result 
        return target;
    }
}

analysis 1

1. When we want to get a binary bit, the simplest way is Shift operator >> or <<, First move i = 0 position , Second move i = 1 position , Just right The first and second bits are taken to , The same goes for the back
2. On this basis , We need to For the result &1, There may be 1 Remove the binary bits of , Only the corresponding one
3. Superposition is enough

analysis 2

1. There can only be two binary cases of elements that have occurred once , namely 0 and 1
   1. If it is 0, result sum % 3 == 0 establish , This binary bit defaults to 0, There is no need to change
   2. If it is 1, result sum % 3 == 0 Don't set up , This binary bit defaults to 0, It needs to be changed to 1, So in the end, as long as the change is 1 The situation of
2. take 1<<i You can get the corresponding binary bit

Algorithm conclusion

The binary solution is superior to the hash counting method , If you don't believe me, you can verify it

The binary solution can not only be used in this problem , It can also be used in the 20 layers of force buckle !