求两个有序列表的交集

Question

我有一个任务给定两个可比较项目的排序列表，L1和L2。你可以假设在L1和L2所有元素都是不同的(没有重复)，但tL1和L2之间的截取可能为非空。

(b)实施一种有效的方法Java计算对称差分(∆)L1与L2之间，L1∆L2。请记住集合论，对称的两个集合A和B的差值是A或B中不同时存在的元素的集合。例子:假设一个={1、3、5、7、9}和B ={1, 2, 3, 4, 5},∆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

想想这个。List1 {1,2,3,5}列表2{1,5}。正如shmosel所说，如果循环运行两次会发生什么?它退出循环，然后函数。理想情况下，您希望遍历数组中的所有元素。

顺便说一句，我不认为你的解决方案是工作得很好(你当然可以，但你的代码将看起来超级丑陋，可能需要0(清单1)。长度* list2.length))。由于两个列表都已排序，因此可以比较两个元素，并先循环较小的元素列表。例如，使用list1和list2，比较1和1，它们都相等，然后移动到2和5。然后比较2和5，将2添加到列表中，并将2移动到3 ONLY。这需要O(list1)长度+ list2.length).

Answer 2

这是一个典型的陷阱。当一个列表耗尽时，循环停止(应该如此)。在这一点上，您仍然需要用尽其他列表。因此，在while循环之后，插入逻辑来从另一个列表复制剩余的元素。因为你知道一个列表已经完成了，只有一个列表还有剩余的元素，但你不知道是哪个，简单的解决方案就是从两个列表中取出剩余的元素。由于两个列表都已排序，因此您知道列表中仍有元素的其余部分不可能包含干链表中的任何元素，因此只需将它们全部添加到结果中。总而言之，你可能会在循环之后加上两个while循环，一个用于iterL1，一个用于iterL2。因为每一个都在线性时间内运行，所以您的时间复杂度不会受到影响。