Leetcode daily practice (main elements)

The title is as follows ：

More than half of the elements in an array are called major elements . To give you one Integers Array , Find out the main elements . If there is no , return -1 . Please design the time complexity as O(N) 、 The space complexity is O(1) Solutions for .

The topic is to find out the main elements of an integer array , The number of the main elements is more than half the length of the array , And the time complexity is O(N), The first solution we thought of was to get the number of each element in the array , To determine whether there is a number of elements more than half the length of the array , If you have any , The main elements are found ; If there is no , There are no major elements , return -1.

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 in , Then quantity plus 1
                Integer count = map.get(num);
                map.put(num, ++count);
            } else {
    
                //  if map Does not exist in the , Deposit in map, The number of 1
                map.put(num, 1);
            }
        }

        AtomicInteger mainNum = new AtomicInteger(-1);
        //  Traverse map aggregate , Check to see if there are more than half the length of the array 
        map.forEach((k, v) -> {
    
            if (v > nums.length / 2) {
    
                //  If there is such a number , Find the main elements 
                mainNum.set(k);
            }
        });
        //  If it does not exist , Go straight back to -1
        return mainNum.get();
    }

Commit the code to LeetCode, The test passed ：

Although the test passed , But the problem is still not perfect , Two iterations greatly reduce the execution efficiency , So is there any way to improve efficiency ？

We can use Boyer-Moore Voting algorithm , The idea is to remove two different elements from the array , Until the voting process can't continue , At this point, the array is empty or the remaining elements in the array are equal .

What does that mean ？ Imagine , Since the number of main elements is more than half of the array length , Then its number must be greater than the sum of other elements except the main elements , If each non major element and each major element are allowed to offset each other , So what's left in the end must be the main elements , such as ：

For such an array , Let's first define a count Variable is used to record the number of main elements , Let's first assume that the first element of an array is the primary element ：

And then go back and forth ：

here count The value of is 3, Continue to traverse and find that the value is 2, At this time let count reduce 1：

Traverse to the 3 A numerical 2 when ,count The value is 0, That's enough to show the value 1 It must not be the main element , Let's assume that the next value is the main element ：

In this way, we have successfully obtained that the main element is 2.

Let's take a more complicated example ：

First, let's assume that the value 1 Is the main element , It turns out that the next value is 2,count reduce 1：

At this point, the element before the position is proved （ Include current location ） Are not primary elements （ It should be noted that only before the current position can it be considered as not the main element ）, Then assume the next value 5 Is the main element ,count Add 1：

It turns out that the next value is 9,count reduce 1：

At this point, assume the next value 5 Is the main element , And so on , until ：

It turns out that the next value is 5,count Add 1：

The next value is still 5,count Add 1：

From this we can find a rule , When count by 0 when , Let's assume that the current position element is the main element , If the next element is equal to it , be count Add 1; If it's not equal , be count reduce 1, When count Reduced to 0 when , To reexamine the new main elements , After the traversal is over , if count Greater than 0, Then assume that the main element is the main element in the array ; if count No more than 0, There are no major elements .

But this is not absolute , such as ：

First, let's assume that the value 1 Is the main element ：

It turns out that the next value is 2,count reduce 1, Down to 0：

Now let's go to the next value 3 As the main element , But in fact, there are no major elements in this array .

Let's take a more vivid example , If there is war in many countries , The way of war is very simple and crude , Every country sends one soldier to fight each other , One result at a time , It's the same death , In the end, as long as there are people on either side , So the country that survives is the country with the largest number of people in the war . But in fact , If other countries lose both sides , But the country that sent only one soldier won , Can we say that this country has the largest number of soldiers ？

So the algorithm is vulnerable to this requirement , So , We need to find out the main elements , Check again , Check it out count Is greater than half the length of the array , If it is , It's 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;
        //  Traversal array 
        for (int num : nums) {
    
            //  if count = 0, Assume that the current element is the main element 
            if (count == 0) {
    
                mainNum = num;
            }
            if (mainNum == num) {
    
                //  If the current element equals the main element , be count Add 1
                count++;
            } else {
    
                //  If not equal to , be count reduce 1
                count--;
            }
        }
        //  here mainNum That is the main element , Check it again 
        count = 0;
        for (int num : nums) {
    
            if (mainNum == num) {
    
                count++;
            }
        }
        if (count > nums.length / 2) {
    
            return mainNum;
        } else {
    
            return -1;
        }
    }

The test passed ：