java - 不同大小列表的交集

Question

我在面试中有这个任务。我以为很简单，但是...
我有两个 list :

List<String> l1 = List.of("A", "B", "A", "A");
List<String> l2 = List.of("A", "C", "A");

我需要找到这两个列表中的共同点。
当然，我试过这个解决方案:

List<String> l1 = List.of("A", "B", "A", "A");
List<String> l2 = List.of("A", "C", "A");
Set<String> l3 = new HashSet<>(l1);
l3.retainAll(l2);
System.out.println(l3); // outputs A

和这个:

List<String> l1 = List.of("A", "B", "A", "A");
List<String> l2 = List.of("A", "C", "A");
List<String> l3 = new ArrayList<>(l1);
l3.retainAll(l2);
System.out.println(l3); // outputs A, A, A

但我只需要输出 A, A我能做什么？

Answer 1

似乎需要首先计算输入列表中每个元素的“频率”，然后重建包含频率较低元素的列表，例如:

Map<String, Integer> map1 = l1.stream().collect(Collectors.groupingBy(x -> x, Collectors.summingInt(x -> 1)));
Map<String, Integer> map2 = l2.stream().collect(Collectors.groupingBy(x -> x, Collectors.summingInt(x -> 1)));

List<String> intersection = map1.entrySet().stream()
        .filter(e -> map2.containsKey(e.getKey())) // filter out missing keys
        .flatMap(e -> Collections.nCopies(
            Math.min(e.getValue(), map2.get(e.getKey())), e.getKey()
            ).stream()
        )
        .collect(Collectors.toList());

System.out.println(intersection);

更简单的解决方案可能是使用普通 groupingBy立即获取子列表并比较子列表的大小以选择较短的子列表:

Map<String, List<String>> map1 = l1.stream().collect(Collectors.groupingBy(x -> x));
Map<String, List<String>> map2 = l2.stream().collect(Collectors.groupingBy(x -> x));

List<String> intersection2 = map1.entrySet().stream()
        .flatMap(e ->
            (e.getValue().size() < map2.computeIfAbsent(
                e.getKey(), (k) -> Collections.emptyList()                    
            ).size() ? e.getValue() : map2.get(e.getKey())
        ).stream())
        .collect(Collectors.toList());

使用 Stream.filter不需要修改 map2与 compute/computeIfAbsent :

List<String> intersection3 = map1.entrySet().stream()
        .filter(e -> map2.containsKey(e.getKey()))
        .flatMap(e ->
                (e.getValue().size() < map2.get(e.getKey()).size() 
                    ? e.getValue() : map2.get(e.getKey()))
                .stream()
        )
        .collect(Collectors.toList());