现在的位置: 首页 > 综合 > 正文

Java 两个有序集合 求交集 差集

2018年02月11日 ⁄ 综合 ⁄ 共 2738字 ⁄ 字号 评论关闭
条件: sourceList  targetList

方法一:

用java集合:
 List<TaskEntity> cloneSourceList = new ArrayList<TaskEntity>(sourceList);

 sourceList.retainAll(targetList); // 此时sourceList已是两者交集

 cloneSourceList.removeAll(sourceList); // 此时sourceList已是source差集

 targetList.removeAll(sourceList); // 此时targetList已是 target差集
方法二:没有使用两个有序list的优越性

       int sourceSize
= sourceList.size();
        int targetSize
= targetList.size();
        List<T> originUpdateList = new ArrayList<T>();
        for (int i
= 0; i < sourceSize; i++) {
            T source = sourceList.get(i);
            boolean flag
=
 true ;
            T target = null;
            for (int j
= 0; j < targetSize; j++) {
                target = targetList.get(j);
                if (source.getID()
== target.getID()) {
                    flag = false;
                    originUpdateList.add( source);
                    if (!source.toString().equals(target.toString()))
{
                        updateList.add( source);
                    }
                    break;
                }
            }
            if (flag)
{
                insertList.add( source);
            }
        }
        targetList.removeAll(originUpdateList); //
此时targetList为要删除的list
        for (T
t : targetList) {
            deleteList.add(t.getID());
        }
     此方法可以直接求出交集、sourceList的差集;但是targetList的差集还需要通过集合

方法三:用归并排序法:

        

int sourceSize = sourceList.size();
        int targetSize = targetList.size();
        int start = 0;
        for (int i = 0; i < sourceSize;) {
            T source = sourceList.get(i);

            for (int j = start; j < targetSize; j++) {
                T target = targetList.get(j);
                if (i >= sourceSize) {
                    deleteList.add(target.getID());
                    System.out.println("%^%^%" + target.getID());
                    continue;
                }
                if (source.getID() < target.getID()) {
                    System.out.println("insert" + source.getID() + "i" + i);
                    insertList.add(source);
                    i++;
                    if (i < sourceSize) {
                        System.out.println("oooooooooooooooooooo");
                        break;
                    } else {
                        deleteList.add(target.getID());
                        System.out.println("999999999999999999");
                        continue;
                    }
                } else if (source.getID() == target.getID()) {
                    if (!source.toString().equals(target.toString())) {
                        updateList.add(source);
                    }
                    System.out.println("*********@@@@@@@@@@@@@@@@@@@@@@@@@@*" + source.getID());
                    i++;
                    if(i>=sourceSize){
                        continue;
                    }
                    start++;
                    break;
                } else if (source.getID() > target.getID()) {
                    System.out.println("%^%^!!!!!!!!!!!!!!!!!!%" + target.getID());
                    deleteList.add(target.getID());
                    start++;
                    if (start >= targetSize) {
                        break;
                    }
                }
            }
            if (start >= targetSize) {
                insertList.add(source);
                i++;
            }
        }



方法三  时间复杂度nlogn
方法二 类似n方。。。其实我也不确定

抱歉!评论已关闭.