Majority element ii[molar voting method for finding modes]

Preface

seek K The number of , The intuitive approach is hash Record , Then take the largest number K individual . And for mode , The time and space can be reduced to O(n)/O(1).
Of course , The premise is that you can analyze the mode problem , Some questions are implicit .

One 、 Most elements II

Two 、 intuitive hash| Moore voting

1、 intuitive hash

//  Every three numbers have it , It means that this number is the most 2 individual , least 0 individual .
    //  Calculation of violence 
    public List<Integer> majorityElement(int[] nums) {
    
        int n = nums.length;
        int bound = n / 3;

        Map<Integer, Integer> fx = new HashMap<>();

        List<Integer> ans = new ArrayList<>();
        for (int num : nums) fx.put(num, fx.getOrDefault(num, 0) + 1);

        for (Map.Entry<Integer, Integer> entry : fx.entrySet()) if (entry.getValue() > bound) ans.add(entry.getKey());

        return ans;
    }

2、 Moore voting

//  Every three numbers have it , It means that this number is the most 2 individual , least 0 individual .
    //  Since there are 0-2 individual , Just use the voting method first , Select the two most elements , Again for The actual number of circular records , Finally, determine whether the two are greater than  n/3, To make sure it's 0/1/2 individual .
    public List<Integer> majorityElement2(int[] nums) {
    
        int el1 = 1 << 31, el2 = 1 << 31;// Two elements .
        int v1 = 0, v2 = 0;// Number of votes for both 
        //  vote , Determine who the top two elements are ？
        for (int num : nums) {
    
            //  notes ： Here we must first determine whether there are equal .
            if (num == el1) ++v1;
            else if (num == el2) ++v2;
            else if (v1 == 0) {
    
                el1 = num;
                ++v1;
            } else if (v2 == 0) {
    
                el2 = num;
                ++v2;
            } else {
    
                --v1;
                --v2;
            }
        }
        //  Calculation , Determine the two maximum elements , What is its actual number .
        v1 = v2 = 0;
        for (int num : nums) {
    
            if (num == el1) ++v1;
            if (num == el2) ++v2;
        }
        //  determine , See if the largest element satisfies the condition .
        int bound = nums.length / 3;
        List<Integer> ans = new ArrayList<>();
        if (v1 > bound) ans.add(el1);
        if (v2 > bound) ans.add(el2);
        //  return , Return the element that finally meets the condition .
        return ans;
    }

summary

1） Moore voting solves a class of mode problems .

reference

[1] LeetCode Most elements II