JZ28-数组中出现次数超过一半的数字

class Solution {
    //HashMap暴力
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (map.containsKey(array[i])) {
                map.put(array[i], map.get(array[i]) + 1);
            } else {
                map.put(array[i], 1);
            }
        }
        List<Integer> list = new ArrayList<>();
        map.forEach((k, v) -> {
            if (v > array.length / 2) {
                list.add(k);
            }
        });
        if (list.size() != 0) {
            return list.get(0);
        } else {
            return 0;
        }
    }
    //排序后暴力
    public int MoreThanHalfNum_Solution2(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }

        Arrays.sort(array);

        int target = array[array.length >> 1];
        int count = 0;

        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                count++;
            }
        }
        if (count > (array.length >> 1)) {
            return target;
        } else {
            return 0;
        }
    }

    public int MoreThanHalfNum_Solution3(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        //用target记录上一次访问的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；如果不同count--，
        int target = array[0];
        for (int i = 1, num = 1; i < array.length; i++) {
            if (target == array[i]) {
                num++;
            } else {
                num--;
            }
            // 减到0的时候就要更换新的preValue值了，
            if (num == 0) {
                target = array[i];
                num = 1;
            }
        }
        //需要判断是否真的是大于1半数，这一步骤是非常有必要的，因为我们的上一次遍历只是保证如果存在超过一半的数就是preValue，
        // 但不代表preValue一定会超过一半
        int num = 0;
        for (int val : array) {
            if (val == target) {
                num++;
            }
        }
        return num > array.length / 2 ? target : 0;
    }
}