而不是交叉兩個列表如何相交超過兩個？

所以結構是{{Dog,Cat,Human},{Human,Dog,Whale,rabbit,Cow},{Monkey,Human,Dog}}。而不是交叉兩個列表如何相交超過兩個？

輸出應爲：Dog,Human。

我不得不在更大的列表中找到列表元素的交集。以前，我看過代碼找到單獨的ArrayLists的交叉點，但不知道如何在同一個ArrayList（兩個以上）內完成。

對於單獨的ArrayLists下面的代碼工作。但我怎麼讓它在一個更大的ArrayList內的多個ArrayLists工作？我在接受採訪時被問到了這一點。曾爲單獨的列表工作，但無法將其列爲同一個ArrayList。

面試官明確聲明只能與字符串一起工作，所以我在澄清後將我的通用類型令牌從{<T>}修改爲{<String>}。

public class Test { 

    public <String> List<String> intersection(List<String> list1, List<String> list2) { 
     List<String> list = new ArrayList<>(); 

     for (String t: list1) { 
      if(list2.contains(t)) { 
       list.add(t); 
      } 
     } 

     return list; 
    } 
public static void main(String[] args) throws Exception { 

     List<String> list1 = new ArrayList<String>(Arrays.asList("Dog", "Cat", "Human")); 
     List<String> list2 = new ArrayList<String>(Arrays.asList("Human", "Dog", "Whale", "rabbit", "Cow")); 

     System.out.println(new Test().intersection(list1, list2)); 

    } 
}

這產生了兩個單獨的ArrayLists正確的輸出。然而，如果輸入稍作修改，例如，對於輸入a,a,a和a,a,，交集方法將返回a,a,a，但是其將輸入a,a和a,a,a給出a,a。邏輯假設是它應該始終返回a,a而不管參數的順序如何。

有關我如何解決這個問題的任何建議，不管輸入順序如何？我怎麼能找到一個更大的列表內的幾個列表（超過兩個）的交集？

來源

2017-07-15 coder1532

提供你有一個工作'intersection'功能，你可以多次找到列表之間的交集返回的交點，以及新的列表。在面向功能的語言中，您只需使用'intersection'來摺疊/減少列表的列表。 – Carcigenicate

如果列表已排序，則可以使用拉鍊技術在「O（n）」中實現它。在每個列表上放置一個標記，最初分別位於索引0處。比較所有值，如果不同，則在顯示較小值的所有列表上推進標記。繼續，直到標記到達列表的末尾（一個足夠交叉）。例如，*信息檢索*中常用的技巧。 – Zabuza

所有你需要做的就是重複調用交會法在此着衣

import java.util.List; 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Iterator; 
public class HelloWorld{ 

public static void main(String []args){ 
    List<String> list1 = new ArrayList<String>(Arrays.asList("Dog", "Cat", "Human")); 
    List<String> list2 = new ArrayList<String>(Arrays.asList("Human", "Dog", "Whale", "rabbit", "Cow")); 

    List<List<String>> lists=new ArrayList<List<String>>(); 

    lists.add(list1); 
    lists.add(list2); 
    Iterator<List<String>> iterator=lists.iterator(); 
    List<String>intersect=null; 
    while(iterator.hasNext()){ 
     List<String> current=iterator.next(); 
      if(intersect==null){ 
       intersect=current; 
      } 
      else{ 
       intersect=intersection(intersect,current); 
      } 
    } 
    System.out.println(intersect); 
} 

public static List<String> intersection(List<String> list1, List<String> list2) { 
    List<String> list = new ArrayList<>(); 

    for (String t: list1) { 
     if(list2.contains(t)) { 
      list.add(t); 
     } 
    } 

    return list; 
}

}

來源

2017-07-15 18:27:08

我喜歡這種方法。但是，這在某種程度上不起作用。你可以請執行它並檢查。 – coder1532

@ coder1532看看我把整個代碼。如果你喜歡我的解決方案，請接受它並加註。 –

Works @JoeyPinto – coder1532

可以使用Stream和filter相交名單：

List<String> list1 = new ArrayList<String>(Arrays.asList("Dog", "Cat", "Human")); 
List<String> list2 = new ArrayList<String>(Arrays.asList("Human", "Dog", "Whale", "rabbit", "Cow")); 
System.out.println(list1.stream() 
      .filter(list2::contains) 
      .collect(Collectors.toList()));

OUTPUT：

[Dog, Human]

來源

2017-07-15 18:19:18 alfasin

他說十字路口不是工會 –

@JoeyPinto感謝您的糾正。固定！ – alfasin

不錯的工作@alfasin，但這將如何工作多個列表？ –

交集是associative，可以實現兩個列表的交集，然後重複應用相同的算法剩下的名單。

Java提供了通過retainAll操作做一個路口的內置方式：

List<String> a = ... 
List<String> b = ... 
List<String> c = ... 
List<String> intersection = new ArrayList<>(a); 
intersection.retainAll(b); 
intersection.retainAll(c);

來源

2017-07-15 18:20:30 dasblinkenlight

工程..這種方式甚至不需要單獨的方法。 – coder1532

假設intersection作品，只是用intersection倍列表清單：

List<ArrayList<String>> lists = /* Lists of lists here */; 

List<String> finalIntersection = 
    lists.stream() 
     .reduce(intersection) 
     .collect(Collectors.toList())

未經檢驗的，但提供intersection的類型與reduce預期的類型匹配，並且reduce有一個允許累加器作爲第一個元素啓動的過載，它應該工作。

不幸的是，由於Java只有流的reduce方法，此解決方案臃腫。在Clojure中（其他JVM語言），代碼大致相當於片斷，簡直是：

(reduce intersection lists)

這僅僅是可愛。

來源

2017-07-15 18:26:44 Carcigenicate

而不是交叉兩個列表如何相交超過兩個？

回答

相關問題