Java线性时间算法：找出数组中出现至少k次的最小整数

你的代码思路方向是对的，但漏掉了k=1的场景处理——当k=1时所有元素都满足条件，但你的代码只在元素重复出现（计数增加）时才判断是否达标，第一次出现的元素（计数为1）没有被纳入候选，导致最终返回Integer.MAX_VALUE而非数组中的最小元素。

另外我们可以用HashMap.getOrDefault()简化代码，去掉冗余的分支判断，让逻辑更清晰。

修正后的代码 #

private static int problem1(int[] arr, int k) {
    HashMap<Integer, Integer> countMap = new HashMap<>();
    int smallest = Integer.MAX_VALUE;
    
    for (int num : arr) {
        // 更新当前数字的计数：存在则+1，不存在则初始化为1
        int currentCount = countMap.getOrDefault(num, 0) + 1;
        countMap.put(num, currentCount);
        
        // 只要当前计数达到k，就尝试更新最小符合条件的数
        if (currentCount >= k) {
            smallest = Math.min(smallest, num);
        }
    }
    
    return smallest;
}

关键改进点 #

• 用getOrDefault替代containsKey判断，一行完成计数更新，代码更简洁。
• 每次更新计数后立即判断是否达标，包括第一次出现的元素，完美解决k=1的场景。
• 变量名更具语义化（countMap、smallest），提升代码可读性。

原代码失败的核心原因 #

举个典型反例：测试用例arr = [3,1,2], k=1

• 遍历3时，原代码将计数设为1，但没有判断1 >= 1，ans保持Integer.MAX_VALUE。
• 遍历1和2时同样跳过判断，最终返回错误的Integer.MAX_VALUE，而正确答案是1。

修正后的代码会在每次计数更新后检查，第一次遇到3就把smallest设为3，遇到1时更新为1，遇到2时保持1，最终返回正确结果。

内容的提问来源于stack exchange，提问作者puyopop