题解 | #数组中出现次数超过一半的数字#TOP51

思路:
1.排序，但是时间复杂度O(n)达不到
2.以第一个数为基准点，开始计数times=1,如果他是众数，超过一半，那么times不可能为0。
网上称为候选人法。如果两个数不相等，顶多消除一个众数和一个非众数，剩下的还是有众数。或者消除两个非众数

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //方法1 遍历 放到map中，计数，再遍历map  计数大于一半就是。 空间O（n）
        //方法 2 排序 或者 +二分法 时间o(n2)
        //这两种方法都不满足题目要求的时间 空间复杂度
        //选择插入排序 最好的情况是 O(N) 虽然用Map最好的情况空间复杂度可以忽略不计
        if(array == null){
            return 0;
        }
//         for(int i = 1;i< array.length;i++){
//             int value = array[i];
//             int j = i - 1;
//             for(;j>= 0;j--){
//                 if(value < array[j]){
//                     array[j + 1] = array[j];
//                 }else{
//                     break;
//                 }
//             }
//             array[j+1] = value;
//         }
        
//         int midNum = array[array.length / 2];
//         int count = 0;
//         for(int item : array){
//             if(item == midNum){
//                 count ++;
//             }
//         }
//         if(count > array.length / 2){
//             return midNum;
//         }
//         return 0;
        return getNumber(array);
    }
    private int getNumber(int[] array){
        if(array == null){
            return 0;
        }
        int times = 1;
        int temp = array[0];
        for(int i = 1 ;i < array.length; i++){
            if(times == 0){
                temp = array[i];
                times = 1;
            }else if(array[i] == temp){
                times ++;
            }else{
                times --;
            }
        }
        return temp;
    }
}