Нахождение пересечения 2 отсортированных списков

Question

У меня есть задание для двух отсортированных списков сопоставимых предметов, L1 и L2. Можно предположить, что в L1 и L2 все элементы разные (без дубликатов), но перехват между L1 и L2 может быть не пустым.

(b) Реализуйте эффективный метод в Java для вычисления симметричной разности (∆) между L1 и L2, L1 ∆L2. Пожалуйста, помните, что в теории множеств симметричная разность двух множеств A и B является множеством элементов либо в A, либо в B, но не в обоих. Пример: предположим, что A = {1,3,5,7,9} и B = {1,2,3,4,5}, A ∆ B = {2,4,7,9}.

Я написал это до сих пор, но я не знаю, почему он останавливает поиск в конце первого списка и не продолжает проверять второй список на различия. Любая помощь?

    public static <AnyType extends Comparable<? super AnyType>>
        void symDifference(List<AnyType> L1, List<AnyType> L2,
                List<AnyType> Difference) 
{

    ListIterator<AnyType> iterL1 = L1.listIterator();
    ListIterator<AnyType> iterL2 = L2.listIterator();
    AnyType itemL1 = null;
    AnyType itemL2 = null;

    if (iterL1.hasNext() && iterL2.hasNext()) 
    {
        itemL1 = iterL1.next();
        itemL2 = iterL2.next();
    }

    while (itemL1 != null && itemL2 != null) 
    {
        int compareResult = itemL1.compareTo(itemL2);
        if (compareResult == 0) 
        {
            itemL1 = iterL1.hasNext() ? iterL1.next() : null;
            itemL2 = iterL2.hasNext() ? iterL2.next() : null;
        } 
        else if (compareResult < 0) 
        {
            Difference.add(itemL1);
            itemL1 = iterL1.hasNext() ? iterL1.next() : null;
        } 
        else
        {
            Difference.add(itemL2);
            itemL2 = iterL2.hasNext() ? iterL2.next() : null;
        }
    }
}

public static void main(String[] args)
{
    LinkedList<Integer> list1 = new LinkedList<>();
    LinkedList<Integer> list2 = new LinkedList<>();
    LinkedList<Integer> difList = new LinkedList<>();

    list1.add(1);
    list1.add(3);
    list1.add(5);
    list1.add(7);
    list1.add(9);

    list2.add(1);
    list2.add(2);
    list2.add(3);
    list2.add(4);
    list2.add(5);

    symDifference(list1,list2,difList);
    System.out.println(difList);

}
}

Answer 1

Это классическая ловушка. Когда один список иссякает, ваш цикл останавливается (как и должно быть). На этом этапе вы все еще хотите исчерпать другой список. Поэтому после цикла while вставьте логику, чтобы скопировать остальные элементы из другого списка. Так как вы знаете, что один список готов, и только в одном остались элементы, но вы не знаете, какой из них, простое решение - просто взять оставшиеся элементы из обоих списков. Поскольку оба списка были отсортированы, вы знаете, что оставшаяся часть списка, в которой все еще есть элементы, не может содержать никаких элементов из списка "без проверки", поэтому вы просто добавляете их все в свой результат. В общем, вы, вероятно, добавите два цикла while после того, как у вас есть цикл, один для iterL1 и один для iterL2, Поскольку каждый из них работает за линейное время, сложность вашего времени не пострадает.

Answer 2

Ну, подумай об этом. list1 {1, 2, 3, 5} list2 {1, 5}. Как сказал шмосел, что произойдет, если ваш цикл запускается дважды? Выход из цикла и функция. В идеале вы хотите просмотреть все элементы обоих массивов.

Кстати, я не думаю, что ваше решение работает так же хорошо (вы можете, конечно, это сделать, но ваш код будет выглядеть ужасно, вероятно, занимает O(list1.length * list2.length)). Поскольку оба списка отсортированы, вы можете сравнить оба элемента и сначала зациклить меньший список элементов. Например, используя list1 и list2, сравните 1 и 1, оба равны, затем перейдите к 2 и 5. Затем сравните 2 и 5, добавьте 2 к списку и ТОЛЬКО от2 до 3. Который принимает O(list1.length + list2.length).