1. 概述
统计数组中不同元素的出现次数是编程中常见的问题。例如，当我们需要知道某个元素的出现频率最高/最低，或特定元素的出现次数时，这种统计就很有用。
本文将探讨几种在数组中统计元素出现次数的常见解决方案。
2. 统计出现次数
2.1. 约束条件
首先需要明确统计对象：
- 对象类型的元素
- 基本数据类型（如
int、char）
如果是数值类型，还需考虑数值范围：
- 固定的小范围数值
- 整个数值范围（数值稀疏分布）
2.2. 解决方案选择
对于 int 或 char 等基本类型，可以使用固定大小的计数器数组存储频率。这种方法有局限性：计数器数组最大受内存限制，且无法扩展到对象类型。
更通用的解决方案是使用 Map。
3. 使用计数器数组
适用于固定范围内的正整数。
3.1. 统计固定范围内的正整数
假设数值范围是 0 到 n-1，统计出现次数：
static int[] countOccurrencesWithCounter(int[] elements, int n) {
int[] counter = new int[n];
for (int element : elements) {
counter[element]++;
}
return counter;
}
算法很简单：遍历数组，在对应元素的计数器位置递增。
算法复杂度：
- 时间复杂度：*O(n)*（遍历数组）
- 空间复杂度：*O(n)*（取决于输入数组大小）
测试用例：统计前10个数字中 3 的出现次数：
int[] counter = countOccurrencesWithCounter(new int[] { 2, 3, 1, 1, 3, 4, 5, 6, 7, 8 }, 10);
assertEquals(2, counter[3]);
计数器数组的另一个典型应用是统计字符串中字符频率，例如在字符串排列检查中。
3.2. 其他场景和局限性
虽然数组最大尺寸很大，但除非明确知道是有限集合，否则不建议用于频率统计。
对于稀疏分布的数值（如小数）难以使用：
- 小数难以找到合适的存储范围
- 负数可通过偏移量处理（例如范围
[-k, k]）：
在int[] counter = new int[(k * 2) + 1];value + k位置存储计数。
局限性：
- 数值范围可能超出实际需求
- 无法统计对象类型元素
4. 使用 Map
Map 更适合统计出现次数。其大小仅受 JVM 内存限制，能存储大量条目。
与计数器类似，我们递增频率值，但这次是针对 Map 的键。Map 支持对象类型，可通过泛型实现通用键：
static <T> Map<T, Integer> countOccurrencesWithMap(T[] elements) {
Map<T, Integer> counter = new HashMap<>();
for (T element : elements) {
counter.merge(element, 1, Integer::sum);
}
return counter;
}
算法复杂度：
- 时间复杂度：*O(n)*（遍历数组）
- 空间复杂度：*O(m)*（m 为数组中不同元素的数量）
测试用例：统计整数出现次数（Map 支持负数）：
Map<Integer, Integer> counter = countOccurrencesWithMap(new Integer[] { 2, 3, 1, -1, 3, 4, 5, 6, 7, 8, -1 });
assertEquals(2, counter.get(-1));
同样适用于字符串：
Map<String, Integer> counter = countOccurrencesWithMap(new String[] { "apple", "orange", "banana", "apple" });
assertEquals(2, counter.get("apple"));
也可考虑使用 Guava Multiset 存储键对应的频率。
5. 使用 Java 8 Stream
Java 8 起，可通过 Stream 按元素分组统计出现次数。原理与 Map 方案相同，但 Stream 支持函数式编程，可利用并行执行。
统计整数出现次数的示例：
static <T> Map<T, Long> countOccurrencesWithStream(T[] elements) {
return Arrays.stream(elements)
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}
⚠️ 注意：使用数组时需先转换为 Stream。
算法复杂度与 Map 方案相同：
- 时间复杂度：O(n)
- 空间复杂度：O(m)
Stream 的优势可能在于执行速度，但仍需遍历所有输入元素并创建频率 Map。
整数测试用例：
Map<Integer, Long> counter = countOccurrencesWithStream(new int[] { 2, 3, 1, -1, 3, 4, 5, 6, 7, 8, -1 });
assertEquals(2, counter.get(-1));
字符串测试用例：
Map<String, Long> counter = countOccurrencesWithStream(new String[] { "apple", "orange", "banana", "apple" });
assertEquals(2, counter.get("apple"));
6. 总结
本文探讨了数组元素出现次数统计的几种方案：
✅ Map 方案（包括 Stream 实现）最通用，适合大多数场景
✅ 计数器数组仅适用于固定范围内的基本类型整数
❌ 避免用计数器数组处理稀疏数值或对象类型
本文代码可在 GitHub 获取。