Как выполнять операции над множествами в отсортированных списках в Kotlin или Java?

Question

У меня есть два отсортированных списка уникальных элементов, и я хочу найти их разность наборов и установить пересечение быстрым и удобным для кэша способом, например, с помощью C ++ std :: set_difference и std :: set_intersection .

Однако сейчас я работаю в Kotlin и не могу найти соответствующую функциональность. Поскольку стандартная библиотека Kotlin построена поверх стандартной библиотеки Java, приветствуется ответ Java .

Я прочитал это и это великие вопросы и ответы на них, но, насколько я понимаю, они имеют дело только с произвольными наборами, таким образом одобряя сортировку .

То же самое относится к гуаве .

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;
}