Java中高效比较列表元素并查找唯一元素位置的方法

你的原代码问题在于每次调用Collections.frequency(strings, strings.get(i))都会完整遍历整个列表，时间复杂度是O(n²)——当列表元素数量很大时，这种嵌套遍历的耗时会呈指数级增长，完全不适合处理大数据量。

下面是时间复杂度为**O(n)**的高效实现方案，用HashMap统计元素出现频率，分两次遍历完成：

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

public class UniqueIndexFinder {
    public static void main(String[] args) {
        ArrayList<String> strings = new ArrayList<>();
        strings.add("Hi");
        strings.add("Hi");
        strings.add("No");
        
        // 第一步：遍历一次列表，统计每个元素的出现次数
        Map<String, Integer> countMap = new HashMap<>();
        for (String s : strings) {
            // 用getOrDefault简化计数逻辑，不存在则默认0，加1后存入
            countMap.put(s, countMap.getOrDefault(s, 0) + 1);
        }
        
        // 第二步：再次遍历列表，找到第一个出现次数为1的元素的索引
        for (int i = 0; i < strings.size(); i++) {
            if (countMap.get(strings.get(i)) == 1) {
                System.out.println(i); // 输出2
                break; // 找到首个目标就终止循环
            }
        }
    }
}

为什么这个方法更高效？ #

• 第一次遍历仅需O(n)时间完成频率统计，第二次遍历同样O(n)时间查找目标，总时间复杂度为O(n)，远优于原方案的O(n²)。
• 空间复杂度为O(k)，k是列表中不同元素的数量，在大多数场景下都是可接受的。

如果你的Java版本是8及以上，也可以用Stream API简化统计步骤，但性能和上面的方案基本一致：

import java.util.stream.Collectors;
import java.util.function.Function;

// ...
Map<String, Long> countMap = strings.stream()
    .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

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