“This is my 37th day of participating in the First Challenge 2022. For details: First Challenge 2022”

preface

The author in addition to college elective “algorithm design and analysis” and “data structure” is muddle through (doesn’t matter much thought and programming), other time is less on contact algorithm, but with the development time of some underlying code/contact processing mechanism increasingly feel algorithm, the importance of So I decided to start systematic study (mainly brush force buckle on the topic) and sorting, also hope that those who have not started to learn as soon as possible.

A series of articles is included in the algorithm column.

Force button topic link,

Problem description

Given an array of integers, nums, each element appears exactly three times except for one element. Find and return the element that appears only once.

 

Example 1:

Input: nums = [2,2,3,2Copy the code

Example 2:

Input: nums = [0,1,0,1,0,1,100] output: 100Copy the code

 

Tip:

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 – 1
• In NUMS, every element appears exactly three times except one

 

Advanced: Your algorithm should have linear time complexity. Can you do it without using extra space?

Analyze the

Methods a

In this case, the first reaction is to iterate over the elements in the map, with the key being the element and the value being the number of occurrences of the element. We can, in the traversal process, remove from the map what we already know to have occurred three times, so we end up eliminating the traversal map and saving space.

Space complexity O(n) : The worst-case scenario requires last removal from the map except for the target key. So (⌈n/3⌉+1)*2. However, this method requires put and Remove map, hash calculation, and capacity expansion. Therefore, it takes a long time to go through this method.

If the time complexity is O(n), it takes n times to traverse the array and store the map. The code is as follows:

public static int getOnlyOnceNum(int[] nums) {
    Map<Integer, Integer> numCountMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        Integer numCount = numCountMap.get(nums[i]);
        if (numCount == null) {
            numCountMap.put(nums[i], 1);
        } else if (numCount == 2) {
            numCountMap.remove(nums[i]);
        } else {
            numCountMap.put(nums[i], ++numCount);
        }
    }

    for (Integer key : numCountMap.keySet()) {
        return key;
    }
    return 0;
}
Copy the code

Method 2

So is there a way to reduce the space and make a faster trip? If you substitute numbers into the binary world, you can count every bit of the corresponding binary of all numbers using the constraint “every element appears exactly three times except for one element.” Because only one element appears once, So if the digit is divisible into 3 and not equal to 0 then you can determine the position of all the 1s that occur only once, and you can determine the position of all the 1s that occur only once, then you can determine this number. The code is as follows:

public static int getOnlyOnceNum1(int[] nums) { int oneNum = 0; for (int i = 0; i < 32; ++i) { int everyBitCount = 0; for (int num : nums) { everyBitCount += (num >> i & 1); } if (everyBitCount % 3 ! = 0) { oneNum |= (1 << i); } } return oneNum; }Copy the code

Time complexity O(n) : 32 x N

Space complexity O(1)

It can be found that the time complexity of method 2 is not as good as that of method 1, but the operation speed of bit operation is much faster than that of Map, and the space complexity is obviously lower than that of method 1. Therefore, method 2 is better than method 1 in the comprehensive efficiency of time and space.