The number of more than half of the array is printed by the sword

Problem description

There is a number in an array that appears more than half the length of the array , Please find out the number . For example, enter a length of 9 Array of {1,2,3,2,2,2,5,4,2}. Because of the number 2 Appears in the array 5 Time , More than half the length of the array , So output 2. If not, output 0.

Their thinking

There are many ways to solve this problem , It includes the use of HashMap、 Sorting and candidate methods are used to solve problems .
Here is mainly about using candidate method to solve this algorithm problem .

Candidate method

In limine , My first reflection on this problem is to solve it through hash table . When I use HashMap After solving this problem , I don't think this problem should be solved by using hash table .

therefore , I checked the solution to the problem , In the official method of problem solving , See the candidate method , The idea of the specific candidate method is as follows ：

1. First , Set up candidates cnt=-1, And set the number of candidates to count = 0
2. And then iterate through the entire array . Judge if the number of candidates 0, Set the candidate to the current number ; If the number of candidates is greater than 0, Then judge whether the current value is the same as the candidate number , If the same , Then the number of candidates will be count++; If it's not the same , Will count--;
3. After traversing the array , The rest cnt For the temporary mode . You need to traverse the array again , Judge cnt Whether the number of occurrences of the array has been checked .

The realization process of the algorithm

Use HashMap Method

Because using this method is too simple , So I'm not going to explain the idea of solving this problem .

public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0) return 0;
        int len = array.length;
        int mid = len / 2;
        //  establish HashMap Stores the number of digits in the array , Just go through it once 
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<len; i++){
            int m = array[i];
                map.put(m, map.getOrDefault(m, 0)+1);
        }
        for(int key: map.keySet()){
            if(map.get(key) > mid) return key;
        }
        
        return 0;
    }

Use the candidate method to solve

// Candidate method , If a number is modal , Then this number must exist more than any other number , Can offset the other numbers 
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length ==0 ) return 0;
        int len = array.length;
        int mid = len/2;
        int cnt = -1;
        int count = 0;
        
        // Traverse array first , Find the mode 
        for(int i=0; i<len; i++){
            if(count == 0){
                cnt = array[i];
                count ++;
            }else{
                if(cnt == array[i]){
                    count ++;
                }else{
                    count --;
                }
            }
        }
        
        // Get the mode , Then judge whether the number of modes is greater than half of the array 
        count = 0;
        for(int i=0; i<len; i++){
            if(cnt == array[i]) count ++;
        }
        
        if(count > mid) return cnt;
        else return 0;
        
    }