1. What is the Moore vote

Boyer — Moore majority Vote algorithm (Boyer — Moore majority vote algorithm) is a constant spatial time complexity algorithm used to find the majority elements in a group of elements.

The problem prototype of this algorithm is to find the majority of possible elements in the set, which are repeated in the input sequence and account for more than half of the sequence elements. After the first iteration, another iteration should be carried out to count the number of occurrences of the results of the first algorithm iteration and determine whether it is mode. If there are no dominant elements in a sequence, the first result may be an invalid random element. For data stream, it is unlikely to find the element with the highest frequency in the case of sublinear space complexity. For sequences, the number of repetitions of elements may also be low.

The description above is from Wikipedia. The process can be divided into two stages:

(1) Voting stage: that is, the votes of voters are offset.

(2) Counting stage: calculate whether the votes of the last remaining candidate in the contest result are valid.

2, sample

On LeetCode, we have the following problems

(1) Interview question 17.10. Main elements

(2) 169. Most elements

Tao (1) belongs to the case where most elements are not necessarily present, and Tao (2) belongs to the case where most elements are present. In the case of a certain number of elements, we can dispense with the counting phase.

So let’s go straight to problem (1), because problem (2) is covered in problem (1).

The title

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).

Example 1:

Input: [1,2,5,9,5,9,5,5,5] output: 5Copy the code

Example 2:

Input: [3,2] output: -1Copy the code

Example 3:

Input: [2,2,1,1, 2,2] Output: 2Copy the code

Analysis of the

Take example 2, [2, 2, 1, 1, 1, 2, 2]

This is the case where there are most elements. For the case where there are no most elements, such as [1, 2, 3] with an odd number of elements, if we follow the above method, the final major value is 3, this is a wrong answer.

Therefore, in the case that there is not necessarily a majority of elements, after obtaining major, we need to go through it again to count whether the number of occurrences of major in the sequence is greater than N / 2, that is, to verify whether the votes are valid.

coding

class Solution {
    public int majorityElement(int[] nums) {
        int major = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                major = nums[i];
            }
            if (major == nums[i]) {
                count++;
            } else {
                count--;
            }
        }

        count = 0;
        for (int num : nums) {
            if(num == major) { count++; }}return (count <= nums.length / 2)? -1: major; }}Copy the code