两个未排序的列表交集作为列表返回

Question

我的问题是是否有可能获得 2 个未排序的列表，并根据它在第一个列表“List1”中的顺序获得两个列表的交集。

public static List intersection(List A, List B) {

    List outcome = null;

    try {

        outcome = A.getClass().newInstance();

    } catch (Exception e) {};

    LinkedList<Integer> temp = new LinkedList<>();

    LinkedHashSet<Integer> ALinkedSet = new LinkedHashSet<>(A); 

    LinkedHashSet<Integer> BLinkedSet = new LinkedHashSet<>(B);

    // first filter elements into temp

    while (ALinkedSet.size() > 0) { 

        int v = ALinkedSet.removeFirst(); 

        if (BLinkedSet.contains(v)) { 

            temp.addLast(v);      

        }

    }

    // add filtered values back to L1

    while (temp.size() > 0) {     

        outcome.addLast(temp.removeFirst()); 

    }

    return outcome;

}

我正在寻找一种方法来完成这项工作，并且可能将其转换为 O(n)。

这是想出的简单方法。有没有更好的方法将大 O 变成线性？我很确定这至少是 O(n*n)。

public static List Intersection(List A, List B) {

    List outcome = null;

    try {

        tulos = A.getClass().newInstance();

    } catch (Exception e) {};

    LinkedHashSet<Integer> AHashSet = new LinkedHashSet<>(A); 

    LinkedHashSet<Integer> BHashSet = new LinkedHashSet<>(B);

    for(Integer Aitem : AHashSet){

        for(Integer Bitem : BHashSet){

            if(Aitem==Bitem) {

                outcome.add(Aitem);

            }

        }

    }

    return outcome;

}

以下会是线性的吗？

public static List Intersection(List A, List B) {

 List outcome = null;

   try {

        tulos = A.getClass().newInstance();

    } catch (Exception e) {};

 LinkedHashSet<Integer> BHashSet = new LinkedHashSet<>(B);

    for(Object Aitem : A) {

        if(BHashSet.contains(Aitem) && !outcome.contains(Aitem)){

         outcome.add(Aitem);

           }

    }

    return outcome;

}

Answer 1

更新：由于我们只能使用 LinkedHashMaps ......并且列表可以有重复项：创建一个ListEntry类，该类具有该数字在列表中重复的总次数和计数。所以如果 2 出现两次，我们将new ListEntry(number: 2, count: 2);在 LinkedHashMap (LHM) 中创建一个；ListEntry使用第一个列表中的数字填充对象的 LHM&nbsp;；现在，遍历第二个列表，一一查看其数字：如果未找到第二个列表的编号，则继续下一个编号；对于找到的每个数字，将其在 LHM 中的条目放在最前面，将其“已见”计数存储在哈希映射 (&nbsp;numberSeen) 中，并更新另一个计数器 (&nbsp;intersectionCount)，用于跟踪迄今为止看到的总相交数；完成第二个列表的迭代后，LHM 前面有相交的数字；现在，它是微不足道的使用numberSeen和intersectionCount创造你的最终名单。运行时复杂度再次为 O(m + n)，空间复杂度为 O(n)。原回复：假设第一个列表的大小为n，第二个列表的大小为m，这是一个简单直接的解决方案，适用于 O(m + n) 时间和 O(m + n) 空间。取第二个列表并将其所有元素放在映射Integer到的哈希映射中Integer。这是为了跟踪列表中的重复项。如果列表中没有重复项，只需使用散列集；现在迭代第一个列表和列表中的每个元素：如果该元素存在于映射中并且计数为正，则将此元素放入新列表中并减少其在映射中的计数；如果该元素在地图中不存在或计数为 0，则跳至列表中的下一个元素。最后，您的新列表将包含两个列表的交集，按照它们在第一个列表中出现的顺序。总空间 = m 用于哈希图 + n 用于新列表。总时间 = m 用于将元素放入哈希映射 + n 用于迭代第一个列表。因此，O(m + n) 时间和 O(m + n) 空间。

Answer 2

怎么样：LinkedHashSet<Integer> intersection = new LinkedHashSet<>(A).retainAll(new HashSet<>(B));或者在 a 中获取输出List：List<Integer> intersection = new ArrayList<> (new LinkedHashSet<>(A).retainAll(new HashSet<>(B)));实际上，这样做可能就足够了：List<Integer> intersection = new ArrayList<> (A).retainAll(new HashSet<>(B));由于执行了传递的retainAll调用，所以我们只需要转换为a就有恒定的搜索时间。containsCollectionBHashSet编辑：要将您建议的解决方案转换为线性时间解决方案，您应该利用HashSet查找时间：public static List Intersection(List<Integer> A, List<Integer> B)&nbsp;{&nbsp; &nbsp; List<Integer> outcome = new ArrayList<>();&nbsp; &nbsp; Set<Integer> BHashSet = new HashSet<>(B);&nbsp; &nbsp; for(Integer Aitem : A) {&nbsp; &nbsp; &nbsp; &nbsp; if(BHashSet.contains(Aitem)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; outcome.add(Aitem);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return outcome;}