Java非嵌套循环求众数：代码补全后数组重排失效问题

你的代码当前仅能处理有序数组，核心问题是依赖连续元素的计数逻辑，一旦数组重排（元素分散），计数就会中断失效。要实现通用的非嵌套循环（O(n)时间复杂度）求众数，需修改标注的三个位置，同时引入哈希表来统计每个元素的出现频率：

修改后的完整代码 #

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

class Main {
  public static void main(String[] args) {
    int[] arr = {3, 1, 2, 3, 2, 3, 2, 3}; // 重排后的测试数组
    int maxCnt = Integer.MIN_VALUE;
    int mem = arr[0];
    int cur = arr[0];
    int curCnt = 0;// 修改初始值为0，后续由哈希表计数覆盖
    int mode = arr[0];
    Map<Integer, Integer> freqMap = new HashMap<>();
    // 初始化第一个元素的频率
    freqMap.put(arr[0], 1);
    
    int i;
    for(i=1;i<arr.length;i++) {
        cur = arr[i];
        // 更新当前元素的频率
        freqMap.put(cur, freqMap.getOrDefault(cur, 0) + 1);
        if(cur == mem) {
            curCnt = freqMap.get(cur);
        }
        else {
            if(curCnt > maxCnt) {
                mode = mem;
                maxCnt = curCnt;
            }
            // 修改此处：更新mem为当前元素，同步curCnt为其累计频率
            mem = cur;
            curCnt = freqMap.get(cur);
        }
    }
    // 修改此处：最终校验遍历哈希表，确保找到全局最大频率的元素
    int finalMax = maxCnt;
    int finalMode = mode;
    for(Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
        if(entry.getValue() > finalMax) {
            finalMax = entry.getValue();
            finalMode = entry.getKey();
        }
    }
    mode = finalMode;
    maxCnt = finalMax;
    
    System.out.printf("mode = %d%nfreq = %d", mode, maxCnt);
  }
}

关键修改说明 #

1. 初始化curCnt：将curCnt = 1改为curCnt = 0，因为后续计数由哈希表的统计值覆盖，初始值不再依赖第一个元素的单次计数。
2. 更新mem和curCnt：取消注释原代码中的两行，并修改为mem = cur; curCnt = freqMap.get(cur);，确保切换元素时，curCnt取哈希表中当前元素的累计频率，而非重置为1。
3. 最终校验逻辑：原有的if(curCnt > maxCnt)仅校验最后一个元素的频率，扩展为遍历哈希表，确保找到所有元素中出现次数最多的那个，避免遗漏其他元素的频率。

运行效果 #

无论数组是否有序，该代码都能正确统计出出现次数最多的众数及其频率。例如测试数组{3,1,2,3,2,3,2,3}会输出：

mode = 3
freq = 4

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