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

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 ...

...并且列表可以有重复项：

1. 创建一个ListEntry类，该类具有该数字在列表中重复的总次数和计数。所以如果 2 出现两次，我们将new ListEntry(number: 2, count: 2);在 LinkedHashMap (LHM) 中创建一个；

2. ListEntry使用第一个列表中的数字填充对象的 LHM ；

3. 现在，遍历第二个列表，一一查看其数字：

1. 如果未找到第二个列表的编号，则继续下一个编号；

2. 对于找到的每个数字，将其在 LHM 中的条目放在最前面，将其“已见”计数存储在哈希映射 ( numberSeen) 中，并更新另一个计数器 ( intersectionCount)，用于跟踪迄今为止看到的总相交数；

4. 完成第二个列表的迭代后，LHM 前面有相交的数字；

5. 现在，它是微不足道的使用numberSeen和intersectionCount创造你的最终名单。

运行时复杂度再次为 O(m + n)，空间复杂度为 O(n)。

---

原回复：

假设第一个列表的大小为n，第二个列表的大小为m，这是一个简单直接的解决方案，适用于 O(m + n) 时间和 O(m + n) 空间。

1. 取第二个列表并将其所有元素放在映射Integer到的哈希映射中Integer。这是为了跟踪列表中的重复项。如果列表中没有重复项，只需使用散列集；

2. 现在迭代第一个列表和列表中的每个元素：

1. 如果该元素存在于映射中并且计数为正，则将此元素放入新列表中并减少其在映射中的计数；

2. 如果该元素在地图中不存在或计数为 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) 

{

    List<Integer> outcome = new ArrayList<>();

    Set<Integer> BHashSet = new HashSet<>(B);

    for(Integer Aitem : A) {

        if(BHashSet.contains(Aitem)) {

            outcome.add(Aitem);

        }

    }

    return outcome;

}