1. 概述
本文将探讨如何使用Java在数组中查找整数的众数。
在Java中处理数据集时，我们经常需要计算统计指标，如平均值、中位数和众数。众数是数据集中出现频率最高的值。如果没有重复数字，则数据集没有众数。如果多个数字具有相同最高频率，则它们都是众数。
2. 问题理解
算法的目标是找到整数数组的众数。我们来看几个例子：
nums = {1, 2, 2, 3, 3, 4, 4, 4, 5}。该数组的众数是4。
*nums = {1, 2, 2, 1}。该数组的众数是{1, 2}*。
在代码中，我们使用以下示例数组：
int[] nums = { 1, 2, 2, 3, 3, 4, 4, 4, 5 };
3. 使用排序法
查找众数的一种方法是先对数组进行排序，然后找出最频繁的元素。这种方法利用了排序数组中重复元素相邻的特性。代码如下：
Arrays.sort(nums);
int maxCount = 1;
int currentCount = 1;
Set<Integer> modes = new HashSet<>();
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]);
}
}
if (nums.length == 1) {
modes.add(nums[0]);
}
此方法先对输入数组排序，然后遍历数组统计每个数字的频率。它跟踪最高频率的数字并相应更新众数列表。同时处理了数组仅包含一个元素的边界情况。
时间与空间复杂度分析：
- 时间复杂度：*O(n log n)*（排序步骤导致）
- 空间复杂度：最坏情况下*O(n)（若使用归并排序），或O(k)*（仅考虑存储众数的额外空间）
其中，n是数组元素数量，k是众数数量。
4. 使用频率数组法
如果数组中的整数范围已知且有限，频率数组法会非常高效。此方法利用数组索引统计出现次数。实现如下：
Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
int maxFrequency = 0;
for (int frequency : frequencyMap.values()) {
if (frequency > maxFrequency) {
maxFrequency = frequency;
}
}
Set<Integer> modes = new HashSet<>();
for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
if (entry.getValue() == maxFrequency) {
modes.add(entry.getKey());
}
}
该方法用Map统计数组中每个整数的频率，然后确定Map中的最高频率。最后收集所有具有最高频率的整数。
时间与空间复杂度分析：
- 时间复杂度：O(n + m)（平均情况下简化为O(n)，因为m通常远小于n）
- 空间复杂度：*O(m + k)（最坏情况下O(n)*，当所有元素唯一且都是众数时）
其中，n是数组元素数量，m是数组中唯一元素数量，k是众数数量。
5. 使用TreeMap
TreeMap可以提供有序的频率映射，在某些场景下很有用。实现逻辑如下：
Map<Integer, Integer> frequencyMap = new TreeMap<>();
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
int maxFrequency = 0;
for (int frequency : frequencyMap.values()) {
if (frequency > maxFrequency) {
maxFrequency = frequency;
}
}
Set<Integer> modes = new HashSet<>();
for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
if (entry.getValue() == maxFrequency) {
modes.add(entry.getKey());
}
}
此方法与前一节逻辑相同，唯一区别是使用了TreeMap。TreeMap确保元素按排序顺序存储，这对需要有序键的后续操作很有用。
时间与空间复杂度分析：
- 时间复杂度：*O(n log m + m)（平均情况下简化为O(n log m)*）
- 空间复杂度：*O(m + k)（最坏情况下O(n)*，当所有元素唯一且都是众数时）
其中，n是数组元素数量，m是数组中唯一元素数量，k是众数数量。
6. 使用流式处理
处理大型数据集时，可以利用Java的并行流来发挥多核处理器优势。实现逻辑如下：
Map<Integer, Long> frequencyMap = Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(e -> e, Collectors.counting()));
long maxFrequency = Collections.max(frequencyMap.values());
Set<Integer> modes = frequencyMap.entrySet()
.stream()
.filter(entry -> entry.getValue() == maxFrequency)
.map(Map.Entry::getKey)
.collect(Collectors.toSet());
代码使用Java流以函数式风格处理数组，使代码简洁且富有表现力。
首先，将基本类型整数转换为Integer对象以支持泛型流操作，然后使用Collectors.groupingBy()和Collectors.counting()按值分组并统计出现次数。通过Collections.max()找到最高频率。最后，过滤出具有最高频率的条目，并将其键收集到集合中。
此方法高效且利用了Java Stream API的强大功能，以清晰易读的方式查找众数。
时间与空间复杂度分析：
- 时间复杂度：O(n + m)（平均情况下简化为O(n)，因为m通常远小于n）
- 空间复杂度：*O(m + k)（最坏情况下O(n)*，当所有元素唯一且都是众数时）
其中，n是数组元素数量，m是数组中唯一元素数量，k是众数数量。
7. 总结
本文探讨了在数组中查找整数众数的多种方法。每种方法各有优势，适用于不同场景。以下是快速总结，帮助选择合适方案：
- ✅ 排序法：适合中小型数组，简单有效
- ✅ 频率数组法：当数字范围较小时效率极高
- ✅ TreeMap：需要有序频率映射时有用
- ✅ 并行流：适合大型数据集，可利用多核优势
根据具体需求选择合适方法，可以优化Java中查找整数众数的过程。
所有示例的源代码可在GitHub获取。