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

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