当前位置：首页 > 后端开发 > 正文

Java求众数的最快方法是什么？

admin
后端开发
2025-06-26
2958

在Java中求众数（出现次数最多的元素），常用方法包括：，1. 使用HashMap统计元素频率，遍历找出最大值。，2. 先对数组排序，再线性扫描统计连续相同元素的最大频次。，3. 使用流处理结合Collectors.groupingBy进行分组计数。

方法1：HashMap统计频率（推荐）

原理：利用HashMap记录每个元素的出现次数，再遍历找出最大频率对应的元素。
时间复杂度：O(n)
空间复杂度：O(n)

Java求众数的最快方法是什么？第1张

import java.util.*;
public class ModeFinder {
    public static List<Integer> findMode(int[] nums) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        int maxCount = 0;
        List<Integer> modes = new ArrayList<>();
        // 统计频率
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
            maxCount = Math.max(maxCount, frequencyMap.get(num));
        }
        // 找出所有众数（可能多个）
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (entry.getValue() == maxCount) {
                modes.add(entry.getKey());
            }
        }
        return modes;
    }
    public static void main(String[] args) {
        int[] data = {1, 2, 2, 3, 3, 3, 4};
        System.out.println("众数: " + findMode(data)); // 输出 [3]
    }
}

方法2：排序后遍历

原理：先排序数组，再线性扫描统计连续相同元素的频率。
时间复杂度：O(n log n)（排序开销）
空间复杂度：O(1)（不考虑排序的栈空间）

import java.util.*;
public class ModeFinder {
    public static List<Integer> findMode(int[] nums) {
        Arrays.sort(nums);
        List<Integer> modes = new ArrayList<>();
        int currentCount = 1, maxCount = 1;
        // 遍历统计连续元素频率
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                currentCount++;
            } else {
                currentCount = 1;
            }
            if (currentCount > maxCount) {
                maxCount = currentCount;
                modes.clear();
                modes.add(nums[i]);
            } else if (currentCount == maxCount) {
                modes.add(nums[i]);
            }
        }
        return modes;
    }
}

方法3：摩尔投票法（适用于唯一众数）

原理：通过抵消不同元素快速定位可能超过半数的众数，需二次验证。
时间复杂度：O(n)
空间复杂度：O(1)

public class ModeFinder {
    public static int findMajority(int[] nums) {
        int candidate = 0, count = 0;
        // 投票阶段
        for (int num : nums) {
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        // 验证是否超过半数
        count = 0;
        for (int num : nums) {
            if (num == candidate) count++;
        }
        return (count > nums.length / 2) ? candidate : -1; // -1表示无绝对众数
    }
}

方法对比与选择建议

方法	适用场景	优点	缺点
HashMap	通用场景，尤其数据量大且无序	高效稳定，支持多个众数	占用额外空间
排序遍历	数据量小或允许排序	空间复杂度低	排序耗时长
摩尔投票	明确存在唯一众数且占比超50%	空间最优	不适用多个众数场景

关键注意事项

多个众数处理：前两种方法天然支持多个众数（如[1,1,2,2]返回[1,2]），摩尔投票法仅返回一个候选值。
空数组/边界值：代码需添加空数组检查（如if (nums.length == 0) return Collections.emptyList();）。
频率相同：当所有元素频率一致时，整个数组都是众数（如[4,5,6]返回[4,5,6]）。