“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!”

The title is as follows:

Elements that make up more than half of an array are called primary elements. Given an array of integers, find the major elements. If not, return -1. Design a solution whose time complexity is O(N) and space complexity is O(1).

Title description is to find out the main elements in an integer array, the number of the main elements to more than half the length of the array, and the time complexity is O (N), the first thing we think of the solution is to get the number of each element in the array, and then go to determine whether there is an element number more than half the length of the array, if any, is to find the main elements; If not, there is no major element and -1 is returned.

The code is as follows:

public static int majorityElement(int[] nums) {
        // Count the number of each element in the array
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                // If map exists, the quantity increases by 1
                Integer count = map.get(num);
                map.put(num, ++count);
            } else {
                // If the map does not exist, store it in the map. The quantity is 1
                map.put(num, 1);
            }
        }

        AtomicInteger mainNum = new AtomicInteger(-1);
        // Iterate through the map collection to see if the number of elements exceeds half of the array length
        map.forEach((k, v) -> {
            if (v > nums.length / 2) {
                // If such a number exists, the main element is foundmainNum.set(k); }});// If it does not exist, return -1
        return mainNum.get();
    }
Copy the code

Submit the code to LeetCode and the test passes:

Although the test was passed, the problem was still not done perfectly. Two iterations greatly reduced the execution efficiency, so is there any way to improve the efficiency?

We can use the Boyer-Moore voting algorithm, where the idea is to remove two different elements from the array until the voting process cannot continue, at which point the array is empty or all the remaining elements in the array are equal.

What does that mean? If the number of primary elements is more than half the length of the array, the number of primary elements must be greater than the sum of the other elements. If each non-primary element cancels out the primary element in pairs, then the primary element must be left. For example:

For such an array, we first define a count variable to count the number of primary elements. We first assume that the first element of the array is the primary element:

Let’s go back:

The value of count is 3, and the value of count is 2.

When the third value, 2, is iterated, count is 0, which is sufficient to indicate that 1 must not be the primary element, and suppose that the next value is the primary element:

So we have a major element of 2.

Let’s look at a more complicated example:

First, assume that the number 1 is the primary element and find that the next number is 2 and count is reduced by 1:

Prove that none of the elements before this position (including the current position) is the primary element, and assume that the next value 5 is the primary element. Count + 1:

Find that the next value is 9 and count is reduced by 1:

The next value, 5, is assumed to be the primary element, and so on until:

Find the next value is 5, count + 1:

The next number is still 5, count + 1:

When count is 0, we assume that the element at the current position is the primary element, and if the next element is equal to it, count increases by 1. If not, count is reduced by 1. When count is reduced to 0, the new primary element is assumed. At the end of the loop, if count is greater than 0, the assumed primary element is the primary element in the array. If count is not greater than 0, there are no major elements.

But it’s not absolute, as in:

First, assume the value 1 as the primary element:

Find the next value is 2, count is reduced by 1, all the way down to 0:

Let the next number, 3, be the primary element, but there is no primary element in the array.

For example, an image if multiple national war, the war of the way is very simple and crude, each country sent a soldier every time two one-on-one hit, one-on-one hit every time there is only one result, is passionate, last as long as there is where people live, then live the number of the people of that country is most. But in fact, if the other countries fight against each other and the country that sends only one soldier wins, can we say that the country that sends the most soldiers wins?

Therefore, the algorithm has loopholes for this requirement. For this reason, we need to check again after the main element is calculated to check whether its count is greater than half of the length of the array. If so, it can be shown that it is the main element.

The final code is as follows:

public static int majorityElement(int[] nums) {
        // Define the main elements
        int mainNum = -1;
        / / counter
        int count = 0;
        // go through the number group
        for (int num : nums) {
            // If count = 0, the current element is assumed to be the primary element
            if (count == 0) {
                mainNum = num;
            }
            if (mainNum == num) {
                // If the current element is equal to the main element, count is incremented by 1
                count++;
            } else {
                // If not, count is reduced by 1count--; }}// mainNum is the main element
        count = 0;
        for (int num : nums) {
            if(mainNum == num) { count++; }}if (count > nums.length / 2) {
            return mainNum;
        } else {
            return -1; }}Copy the code

Pass the test: