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

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

怎么样：

LinkedHashSet<Integer> intersection = new LinkedHashSet<>(A).retainAll(new HashSet<>(B));

或者在 List 中获取输出：

List<Integer> intersection = new ArrayList<> (new LinkedHashSet<>(A).retainAll(new HashSet<>(B)));

实际上，这样做可能就足够了：

List<Integer> intersection = new ArrayList<> (A).retainAll(new HashSet<>(B));

由于retainAll的执行调用了Collection的contains，所以我们只需要将B转换为HashSet就可以得到常量搜索时间。

编辑：

要将您建议的解决方案转换为线性时间解决方案，您应该利用 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;
}

Answer 2

更新：因为我们只能使用 LinkedHashMaps...

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

创建一个ListEntry class，其中包含数字和数字在列表中重复的总次数。所以如果2出现两次，我们将在LinkedHashMap(LHM)中创建一个new ListEntry(number: 2, count: 2);；
使用第一个列表中的数字填充 ListEntry 个对象的 LHM；
现在，遍历第二个列表，一个一个地检查它的数字：
1. 如果没有找到第二个列表的号码，继续下一个号码；
2. 对于找到的每个数字，将其在 LHM 中的条目放在前面，将其 "seen" 计数存储在哈希映射 (numberSeen) 中，并更新另一个计数器 (intersectionCount)跟踪到目前为止看到的总相交数；
完成第二个列表的迭代后，LHM 前面有相交的数字；
现在使用 numberSeen 和 intersectionCount 并创建您的最终列表是微不足道的。

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

原回复：

假设第一个列表的大小为n，第二个列表的大小为m，这样简单明了在 O(m + n) 时间和 O(m + n) space.

内有效的解决方案

获取第二个列表并将其所有元素放入映射 Integer 到 Integer 的哈希映射中。这是为了跟踪列表中的重复项。如果您的列表中没有重复项，只需使用哈希集即可；
现在遍历第一个列表和列表中的每个元素：
1. 如果该元素存在于地图中且计数为正，则将此元素放入新列表并减少其在地图中的计数；
2. 如果该元素不存在于地图中或计数为 0，则跳至列表中的下一个元素。

最后，您的新列表将包含两个列表的交集，按照它们在第一个列表中出现的顺序排列。

总计 space = 哈希映射的 m + 新列表的 n。

总时间 = m 用于将元素放入 hashmap + n 用于遍历第一个列表。

因此，O(m + n) 时间和 O(m + n) space.

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

Two unsorted lists Intersection returned as a list

java

list

methods

intersection

linkedhashset