java - 如何在 Kotlin 或 Java 中对排序列表进行集合操作？

Question

我有两个已排序的唯一项目列表，我想找到它们的集合差异并以快速且缓存友好的方式设置交集，例如使用 C++ std::set_difference和 std::set_intersection .

但是，现在我在Kotlin中工作，找不到相应的功能。由于 Kotlin 标准库构建于 Java 标准库之上，因此欢迎回答 Java。

我通读了this和 this很好的问题和所有的答案，但据我所知，它们只处理任意集合，因此丧失了排序性。

Guava 也是如此.

Answer 1

这里是在最坏情况下运行 O(n+m) 的合并交叉实现

static <T extends Comparable<T>> List<T> intersect(List<T> list1, List<T> list2) {
    final int size1 = list1.size();
    final int size2 = list2.size();
    final List<T> result = new ArrayList<>(Math.min(size1, size2));

    int i = 0;
    int j = 0;
    while (i < size1 && j < size2) {
        T a = list1.get(i);
        int compare = a.compareTo(list2.get(j));
        if (compare < 0)
            i++;
        else if (compare > 0)
            j++;
        else {
            result.add(a);
            i++;
            j++;
        }
    }

    return result;
}