package com.wyl;
/**
 * 寻找数组中出现次数超过数组长度一般的数组
 * @author wyl
 *
 */
public class MoreThanHalfNum {

    /**
     * 遍历数组的时候保存两个值：一个是数组中的值，一个为次数
     * 遍历数组，如果遍历的下一个数字和之前保存的值不一样时， 次数减1；
     * 如果和之前保存的值相同的时候，次数加1；
     * 如果次数为0时，保存下一个数字，并且次数设为1
     * */
    public int moreThanHalfNum(int[] array, int length){
        if(array == null || length <= 0){ //输入的数组非法
            return 0;
        }
        int number = 0;  //保存数组中的一个数字
        int count = 0; //保存数字出现的次数
        for(int i=0;i<length;i++){
            if(count == 0){
                number = array[i];
                count = 1;
            }else if(array[i] == number){
                count++;
            }else{
                count-- ;
            }
        }
        if(!checkNumMoreThanHalf(array, length, number)){
            return 0;
        }
        return number;
    }

    /**
     * 检查数字number在数组array中出现的次数是否大于一般
     * @param array
     * @param length
     * @param number
     * @return
     */
    private boolean checkNumMoreThanHalf(int[] array, int length, int number) {
        // TODO Auto-generated method stub
        boolean isMoreThanHalf = true;
        int count = 0;
        for(int i=0;i<length;i++){
            if(array[i] == number){
                count++;
            }
        }
        if(count*2 <= length){
            isMoreThanHalf = false; 
        }
        return isMoreThanHalf;
    }
    
    public static void main(String[] args) {
        MoreThanHalfNum moreThanHalfNum = new MoreThanHalfNum();
        int[] a = {1,0,3,0,0,0,5,4,0,3};
        int num = moreThanHalfNum.moreThanHalfNum(a, a.length);
        System.out.println(num);
    }
}