而不是交叉两个列表如何相交超过两个？

问题描述：

所以结构是{{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而不管参数的顺序如何。

有关我如何解决这个问题的任何建议，不管输入顺序如何？我怎么能找到一个更大的列表内的几个列表（超过两个）的交集？

提供你有一个工作'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; 
}

}

我喜欢这种方法。但是，这在某种程度上不起作用。你可以请执行它并检查。 – 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]

他说十字路口不是工会 –

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

工程..这种方式甚至不需要单独的方法。 – 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)

这仅仅是可爱。

而不是交叉两个列表如何相交超过两个？

相关推荐