如何高效统计ArrayList（含嵌套）中元素的出现次数？

给定嵌套结构的ArrayList<ArrayList<Integer>>（无法使用sort()方法），当前已实现通过遍历统计单个值出现次数的方法，但面对长列表且需要统计所有元素出现次数的场景，有以下两个疑问及解决方案：

1. 是否存在更高效的方法统计单个指定值的出现次数？ #

对于单个值的统计，遍历是理论上的最优解——因为必须检查每一个元素才能确认是否匹配，时间复杂度固定为O(n)（n为所有子列表的元素总数）。不过可以用Java 8+的流API简化代码实现，效率和手动遍历持平，但代码更简洁：

// 针对嵌套ArrayList的单个值统计
public int countSingleValue(int searchVal) {
    return myArrayList.stream()
                      .flatMap(List::stream) // 将嵌套列表展平为单一元素流
                      .filter(num -> num == searchVal)
                      .mapToInt(e -> 1)
                      .sum();
}

如果是普通非嵌套的ArrayList<Integer>，移除flatMap(List::stream)即可。

2. 统计所有元素出现次数，是否有更高效的方案？ #

有，使用**哈希表（HashMap）**做一次全局统计，之后查询任意元素的次数都是O(1)操作，远优于每次查询都遍历整个列表的方案。

手动循环实现预处理 #

// 全局存储元素-次数映射，只需初始化一次
private Map<Integer, Integer> elementCountMap = new HashMap<>();

// 预处理统计所有元素的出现次数
public void precomputeAllCounts() {
    for (List<Integer> subList : myArrayList) {
        for (int num : subList) {
            // 若元素已存在则次数+1，否则初始化为1
            elementCountMap.put(num, elementCountMap.getOrDefault(num, 0) + 1);
        }
    }
}

// 查询指定元素的出现次数
public int getElementCount(int searchVal) {
    // 不存在则返回0
    return elementCountMap.getOrDefault(searchVal, 0);
}

Java 8流简化预处理 #

// 一行代码完成统计，返回元素到次数的映射
Map<Integer, Long> elementCountMap = myArrayList.stream()
                                               .flatMap(List::stream)
                                               .collect(Collectors.groupingBy(
                                                   Function.identity(), 
                                                   Collectors.counting()
                                               ));

// 查询时直接取值，不存在则返回0
long count = elementCountMap.getOrDefault(searchVal, 0L);

核心优势：预处理仅需一次O(n)遍历，后续任意次数的查询都是O(1)。如果需要多次查询不同元素，总时间复杂度为O(n + k)（k为查询次数），远优于逐个查询的O(k*n)，尤其适合长列表+多查询的场景。

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