剑指Offer第二十八题：数组中出现次数超过一般的数字

题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解答：
1：阵地攻守的思路：第一个数字作为士兵，count=1，遇到一个相等的数字即友军则count++，遇到不同的数字即敌军则count--，当count==0的时候，选用下一个数字作为友军count=1。直到最后若count >1，那么只有这个数字才有可能是超过一半的数字，因为若一个数字他超过数组一半，那么它必定能活到最后。
public class Solution {

public int MoreThanHalfNum_Solution(int [] array) {
    int length=array.length;
    if(array==null||length<=0){
        return 0;
    }

    int result=array[0];
    int times=1;
    for(int i=1;i<length;i++){
        if(times==0){
            result=array[i];
            times=1;
        }else{
            if(array[i]==result){
                times++;
            }else{
                times--;
            }
        }
    }

    times=0;
    for(int i=0;i<length;i++){
        if(result==array[i]){
            times++;
        }
   }

    if (times * 2 >length) {
        return result;
    }
    return 0;
}

}
2.记录一下自己的弱鸡方法，一开始真觉得这题没啥可做的
public class Q_28 {

public int MoreThanHalfNum_Solution(int[] array) {
    int max = 0;
    int val = 0;
    Map<Integer, Integer> map = new HashMap<>();//hashmap记录遍历的结果
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        Integer mapvalue = map.get(value);
        if (mapvalue != null) {
            map.put(value, mapvalue + 1);
            if (mapvalue + 1 > max) {
                max = mapvalue + 1;
                val = value;
            }
        } else {
            map.put(value, 1);
            if (max < 1) {
                max = 1;
                val = value;
            }
        }

    }
    if (max > array.length / 2) {
        return val;
    }
    return 0;
}
public static void main(String[] args) {
    int[] arr = {1, 2, 3, 1};
    System.out.println(new Q_28().MoreThanHalfNum_Solution(arr));
}

}