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

2020-11-09 22:18:50 Long Tao

# 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;

}
``````