查找2個排序列表的交集

我有的賦值給定兩個可比項目的排序列表， L1和L2。你可以假設在L1和L235中所有的元素都是不同的（不重複），但是他在L1和L2之間的截取可能是非空的。查找2個排序列表的交集

（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); 

} 
}

來源

2016-09-30 Rafael Leal-Mccormack

你試過調試嗎？ – shmosel

你說while循環while（itemL1！= null && itemL2！= null）'。你爲什麼期望它做別的事情？ – shmosel

這是一個經典的陷阱。當一個列表幹運行時，你的循環停止（因爲它應該）。此時您仍然想要耗盡其他列表。提示：既然你知道一個列表已經完成，並且只有一個元素有剩餘，但是你不知道哪一個，簡單的解決方案就是從這兩個列表中取出所有剩餘的元素。 –

好吧，想想這個。列表1 {1,2,3,5} 列表2 {1,5}。 shmosel說，如果你的循環運行兩次會發生什麼？它退出循環和函數。理想情況下，您想要穿過這兩個陣列上的所有元素。

順便說一句，我不認爲你的解決方案工作得很好（你可以的原因，但你的代碼會看起來超級醜，可能需要O（list1.length * list2.length））。由於這兩個列表都是排序的，因此您可以比較這兩個元素，並首先循環更小的元素列表。例如，使用list1和list2，比較1和1，兩者相等，然後移動到2和5.然後比較2和5，將2添加到列表中，並將2移動到3 僅限。這需要O（list1.length + list2.length）。

來源

2016-09-30 01:27:25

但是如果您不知道哪個更大或更小？我所知道的是，它的排序，但列表可以是任何長度。 –

你不需要知道。所有你需要的是：比較list1項目與列表2項目。如果它們相等，list1Item = list1.next（）; list2Item = list2.next（）;如果list1項較大，則list2Item = list2.next（），如果list2項較大則類似。 –

這是一個經典的陷阱。當一個列表幹運行時，你的循環停止（因爲它應該）。此時您仍然想要耗盡其他列表。因此，在while循環之後插入邏輯以從其他列表中複製剩餘的元素。既然你知道一個列表已經完成，並且只有一個元素有剩餘，但是你不知道哪一個，簡單的解決方案就是從這兩個列表中取出剩餘的元素。由於這兩個列表都已排序，因此您知道列表中仍有元素的其餘列表不能包含run-dry列表中的任何元素，因此您只需將它們全部添加到結果中即可。總而言之，您可能會在循環之後添加兩個while循環，一個用於iterL1，另一個用於iterL2。由於每一個都以線性時間運行，您的時間複雜性不會受到影響。

來源

2016-09-30 12:02:32

查找2個排序列表的交集

回答

相關問題