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

• 思路：方法一：通过HashMap记录每个数字出现的次数，但是这种算法需要额外占用一个空间，空间复杂度为O(N)；
  方法二：因为数组中肯定有一个数据是超过一半的，通过数组排序，那么这个数组的中间值肯定是最终的结果
  方法三：利用不同数据相消，最终超过一半数据的结果就会出现。
• 时间：2021年8月12号

import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //方法一：利用HashMap的contains特性，来记录array中相同数字的数量, 因为多开辟了空间，
        //所以不是最优解
        /* Map<Integer, Integer> map = new HashMap<>();
        int len = array.length;
        int num = array[0];
        int max = 0;
        for (int i = 0; i < len; i++) {
            map.put(array[i], map.getOrDefault(array[i], 0) + 1);


            int value = map.get(array[i]);

            if (max < value) {
                max = value;
                num = array[i];
            }
        }

        return num; */

        // 方法二：直接排序，既然有一个众数肯定过半，那么中间数肯定是所求结果
        /* Arrays.sort(array);
        return array[array.length / 2]; */

        //方法三：所有不相同的数字都是一对敌人，每次有不同的数字，则两个同时小时，
        // 留下来的数字就是结果
        int win = 0;
        int count = 0;

        for (int num : array) {
            if (count == 0) {
                win = num;
                count = 1;
            } else {
                if (win == num) {
                    count++;
                } else {
                    count--;
                }
            }
        }

        return win;
    }
}