剑指offer之 数组中出现次数超过一半的数字

public class Solution {
    
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null||array.length==0){
            return -1;
        }
        //使用哈希表
        int mapArr[]=new int[256];
        for(int i=0;i<mapArr.length;i++){
            mapArr[i]=0;
        }
        for(int i=0;i<array.length;i++){
            mapArr[array[i]]++;
        }
        for(int i=0;i<mapArr.length;i++){
            if(mapArr[i]>(array.length)/2){
                return i;
            }
        }
        //没有找到这样的数字
        return 0;
    }
}

　　上面的解法 时间复杂度  空间复杂度较高

public class Solution {
    boolean isInvalid=false;
    
    public int MoreThanHalfNum_Solution(int [] array) {
        
        if(CheckInvalidArray(array,array.length)){
            return -1;
        }
        int result=array[0];
        int count=1;
        for(int i=1;i<array.length;i++){
            if(count==0){
                result=array[i];
                count=1;
            }else if(array[i]==result){
                count++;
            }else{
                count--;
            }
        }
        if(!CheckMoreThanHalf(array,array.length,result)){
            result=0;
        }
        return result;
    }
    //判断数组是否为null或者数组长度为0，我们在这里封装成一个函数，以后多考虑这种用法
    private boolean CheckInvalidArray(int[] arr,int length){
        
        isInvalid=false;
        //输入无效的情况
        if(arr==null||length==0){
            isInvalid=true;
        }
        return isInvalid;
    }
    //判断一个数字的出现次数是否超过数组元素的一半
    private boolean CheckMoreThanHalf(int[] arr,int length,int number){
        int count=0;
        for(int i=0;i<length;i++){
            if(arr[i]==number){
                count++;
            }
        }
        boolean isMoreThanHalf=true;
        if(count*2<=length){
            isInvalid=true;
            isMoreThanHalf=false;
        }
        return isMoreThanHalf;
    }
}