如何求解动态数量嵌套List的交集？（附Java代码示例）

核心思路 #

要处理任意数量子List的交集，最直接的方式是以第一个子List为初始交集，然后依次与后续每个子List求交集，中途如果交集为空可以提前终止，避免不必要的计算。用HashSet来处理交集效率更高，因为它的retainAll方法时间复杂度更低。

基础实现（无重复元素场景） #

这个方法适用于子List中元素无重复，或者只需要判断元素是否存在于所有子List中的场景：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class NestedListIntersection {
    public static List<String> findNestedListIntersection(List<List<String>> nestedList) {
        // 边界判断：空输入直接返回空列表
        if (nestedList == null || nestedList.isEmpty()) {
            return new ArrayList<>();
        }
        
        // 用第一个子List初始化交集集合
        Set<String> intersectionSet = new HashSet<>(nestedList.get(0));
        
        // 遍历剩余的每个子List，逐步求交集
        for (List<String> subList : nestedList.subList(1, nestedList.size())) {
            // retainAll会直接修改集合，只保留同时存在于当前subList中的元素
            intersectionSet.retainAll(subList);
            
            // 交集为空时提前终止循环，节省资源
            if (intersectionSet.isEmpty()) {
                break;
            }
        }
        
        // 将Set转换为List返回（如果需要保持元素原始顺序，可以用LinkedHashSet初始化）
        return new ArrayList<>(intersectionSet);
    }

    public static void main(String[] args) {
        // 你的测试示例
        List<List<String>> x = new ArrayList<>();
        x.add(new ArrayList<>(List.of("1","2","3","4")));
        x.add(new ArrayList<>(List.of("3","4")));
        x.add(new ArrayList<>(List.of("4","5")));
        
        List<String> result = findNestedListIntersection(x);
        System.out.println(result); // 输出: [4]
    }
}

关键细节说明 #

• 边界处理：先判断输入是否为空，避免NullPointerException和无意义的计算。
• 效率优化：用HashSet而非ArrayList处理交集，因为HashSet的retainAll是基于哈希查找，时间复杂度远低于ArrayList的遍历查找。如果需要保留元素的原始顺序，可以用LinkedHashSet初始化。
• 提前终止：当交集变为空时，直接跳出循环，不需要继续遍历后续子List。

进阶实现（处理重复元素场景） #

如果需要考虑元素的出现次数（比如交集要保留所有子List中该元素的最小出现次数），可以用Map统计元素出现次数来实现：

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

public class NestedListIntersectionWithCount {
    public static List<String> findNestedListIntersectionWithCount(List<List<String>> nestedList) {
        if (nestedList == null || nestedList.isEmpty()) {
            return new ArrayList<>();
        }
        
        // 统计第一个子List的元素出现次数
        Map<String, Integer> countMap = new HashMap<>();
        for (String s : nestedList.get(0)) {
            countMap.put(s, countMap.getOrDefault(s, 0) + 1);
        }
        
        // 遍历后续子List，更新元素的最小出现次数
        for (List<String> subList : nestedList.subList(1, nestedList.size())) {
            Map<String, Integer> subCountMap = new HashMap<>();
            for (String s : subList) {
                subCountMap.put(s, subCountMap.getOrDefault(s, 0) + 1);
            }
            
            // 过滤掉不在当前子List中的元素，并更新最小次数
            Iterator<Map.Entry<String, Integer>> iterator = countMap.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<String, Integer> entry = iterator.next();
                String key = entry.getKey();
                if (!subCountMap.containsKey(key)) {
                    iterator.remove();
                } else {
                    entry.setValue(Math.min(entry.getValue(), subCountMap.get(key)));
                }
            }
            
            if (countMap.isEmpty()) {
                break;
            }
        }
        
        // 将统计结果转换为List
        List<String> result = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
            for (int i = 0; i < entry.getValue(); i++) {
                result.add(entry.getKey());
            }
        }
        return result;
    }

    public static void main(String[] args) {
        List<List<String>> x = new ArrayList<>();
        x.add(new ArrayList<>(List.of("4","4","1","2")));
        x.add(new ArrayList<>(List.of("3","4")));
        x.add(new ArrayList<>(List.of("4","4","5")));
        
        List<String> result = findNestedListIntersectionWithCount(x);
        System.out.println(result); // 输出: [4]
    }
}

测试验证 #

运行基础实现的main方法，输入你提供的嵌套List，会输出[4]，正好是三个子List的交集元素。

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