V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
ray0625
V2EX  ›  问与答

求算法~java 多个 list 取交集

  •  
  •   ray0625 · 2015-11-13 17:30:28 +08:00 · 10728 次点击
    这是一个创建于 3288 天前的主题,其中的信息可能已经有所发展或是发生改变。

    项目中遇到这么一个问题:
    现在有 5 个 list ,这 5 个 list 不一定都是有值的,现在要判断哪几个 list 有值,然后从有值的 list 里取交集,自己想了想逻辑,感觉想出来的有点复杂,求大神赋值简单点的算法

    13 条回复    2015-11-17 18:01:21 +08:00
    icegreen
        1
    icegreen  
       2015-11-13 18:06:09 +08:00
    1. 先把有值的筛选出来;
    2. 遍历每个 list,把元素存到 map 中, {元素:出现次数} , map 的 key 是元素,value 是出现次数,
    3. 最后把 value=list 数量的筛选出来;
    yuyue007
        2
    yuyue007  
       2015-11-13 18:15:14 +08:00
    @icegreen 为什么还要用 map 。。。
    yuyue007
        3
    yuyue007  
       2015-11-13 18:18:23 +08:00
    public List<String> xxx(final List<String>... input) {
    List<String> result = new ArrayList<String>();
    if (input == null || input.length == 0) {
    return result;
    }

    for (List<String> item : input) {
    if (item.isEmpty()) {
    continue;
    }

    if (result.isEmpty()) {
    result.addAll(item);
    continue;
    }

    result.retainAll(item);
    }

    return result;
    }


    没测试过,应该没问题。
    kaifeii
        4
    kaifeii  
       2015-11-13 18:23:57 +08:00
    List<List> listList = new ArrayList<List>(5);
    Set tempSet = new HashSet();
    Set resultSet = new HashSet();
    resultSet.addAll(listList.get(0));
    for (int i = 1;i < 5; ++ i){
    tempSet.clear();
    tempSet.addAll(listList.get(i));
    resultSet.retainAll(tempSet);
    }

    这样吧大概,用 set 作交集、并集和差集运算很不错,可以上网查一下。
    icegreen
        5
    icegreen  
       2015-11-13 18:29:12 +08:00
    @yuyue007
    哎呀.....我忘了有 retainAll 这个方法了!!!尴尬;

    不过你这个好像还有点问题, 如果前两个的交集为空,这时候 result 是空的,循环到第三个 list 时候, 就会把第三个 list 全部添加进 result 了;
    hao123yinlong
        6
    hao123yinlong  
       2015-11-13 20:00:50 +08:00
    Java 实现超简单么。。 都不用自己写算法实现

    ```
    /**
    * 从 有值的 list 里取交集
    * @param lists
    * @return
    */
    public List<Object> intersection(List<List<Object>> lists) {
    if(lists == null || lists.size() == 0){
    return null;
    }
    ArrayList<List<Object>> arrayList = new ArrayList<>(lists);
    for (int i = 0; i < arrayList.size(); i++) {
    List<Object> list = arrayList.get(i);
    // 去除空集合
    if (list == null || list.size() == 0) {
    arrayList.remove(list);
    i-- ;
    }
    }
    if(arrayList.size() == 0){
    return null;
    }
    List<Object> intersection = arrayList.get(0) ;
    // 就只有一个非空集合,结果就是他咯
    if(arrayList.size() == 1){
    return intersection;
    }
    // 有多个非空集合,直接挨个交集
    for (int i = 1; i < arrayList.size()-1; i++) {
    intersection.retainAll(arrayList.get(i));
    }
    return intersection;
    }



    public void test() {
    List<Object> list1 = new ArrayList<Object>();
    List<Object> list2 = new ArrayList<Object>();
    List<Object> list3 = new ArrayList<Object>();
    List<Object> list4 = new ArrayList<Object>();
    List<Object> list5 = new ArrayList<Object>();

    initList(list1);
    initList(list2);
    initList(list3, "3", "4", "5");
    initList(list4, "3","4");
    initList(list5, "8","3", "3","4");

    System.out.println(intersection(Arrays.asList(list1,list2,list3,list4,list5)));

    }


    /**
    * 给 List 添加元素
    *
    * @param list
    * @param item
    */
    public void initList(List<Object> list, Object... item) {
    if (list == null) {
    throw new IllegalArgumentException("list can't be empty!");
    }
    if (item == null || item.length == 0) {
    return;
    }
    list.addAll(Arrays.asList(item));
    }

    public static void main(String[] args) {
    new Test().test();
    }

    ```
    chenwj
        7
    chenwj  
       2015-11-13 20:58:49 +08:00
    stream 风格
    ```
    public static List<Element> retainElementList(List<List<Element>> elementLists) {
    checkNotNull(elementLists, "elementLists should not be null!");
    Optional<List<Element>> result = elementLists.parallelStream().filter(elementList -> elementList != null && ((List) elementList).size() != 0).reduce((a, b) -> {
    a.retainAll(b);
    return a;
    });
    return result.orElse(new ArrayList<>());
    }
    ```
    zwy
        8
    zwy  
       2015-11-13 21:01:38 +08:00
    每次看到 JAVA 就心累啊
    ruby 下面只要 setA - (setA - setB) 就好了
    ray0625
        9
    ray0625  
    OP
       2015-11-16 09:51:15 +08:00
    @icegreen @yuyue007 感谢两位,看了一下这个方法应该没问题,如果前两个为空,第三个不为空,就是应该把第三个全部添加进去,再跟后面不为空的做交集
    ray0625
        10
    ray0625  
    OP
       2015-11-16 09:52:12 +08:00
    @hao123yinlong 明白了,谢谢,写的好详细
    ray0625
        11
    ray0625  
    OP
       2015-11-16 09:52:37 +08:00
    @chenwj 这个还真没用过,,,不知道咋用
    chenwj
        12
    chenwj  
       2015-11-16 13:34:35 +08:00
    @ray0625 就是一个简单的 reduce ,关键字搜 java8 stream reduce
    yuyue007
        13
    yuyue007  
       2015-11-17 18:01:21 +08:00
    @icegreen 是的,有问题。反正知道是哪个意思就行了,哈哈。需要改一下初始化第一个被比较元素的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3782 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 05:05 · PVG 13:05 · LAX 21:05 · JFK 00:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.