题解 | #数组中出现次数超过一半的数字#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here

        // 核心思想：创建哈希表统计对应元素的出现次数
        // 算法的实践复杂度O(N)，空间复杂度O(N)（空间复杂度为O(1)的方法暂时没有想出来）

        // 1.创建哈希表
        HashMap<Integer, Integer> hm = new HashMap<>();

        // 2.遍历数组，记录哈希表
        for (int cur : numbers) {
            if (hm.containsKey(cur)) {
                // 表中记录过当前key
                int count = hm.get(cur);
                count++;
                hm.put(cur, count);
            } else {
                // 表中没有及路过当前key
                hm.put(cur, 1);
            }
        }

        // 3.找到表中出现次数最高的那个key
        int max = 0;
        int result = numbers[0];
        // 3.1 将Map转化成Set，然后使用for遍历，方便使用外部的变量记录结果（匿名内部类不能使用外部变量记录）
        Set<Map.Entry<Integer, Integer>> entrySet = hm.entrySet();
        for (Map.Entry<Integer, Integer> entry : entrySet) {
            if (entry.getValue() > max) {
                max = entry.getValue();
                result = entry.getKey();
            }
        }

        return result;
    }
}