java - 在字符串链表的链表中查找重复项的最有效方法 - java

Question

假设我们有一个字符串链接列表的链接列表。

LinkedList<LinkedList<String>> lls = new LinkedList<LinkedList<String>> ();
LinkedList<String> list1 = new LinkedList<String>(Arrays.asList("dog", "cat", "snake"));
LinkedList<String> list2 = new LinkedList<String>(Arrays.asList("donkey", "fox", "dog"));
LinkedList<String> list3 = new LinkedList<String>(Arrays.asList("horse", "cat", "pig"));
lls.add(list1);
lls.add(list2);
lls.add(list3);

正如您所看到的，这 3 个字符串链表是不同的，但也有一些共同的元素。我的目标是编写一个函数，将每个列表与其他列表进行比较，如果至少有一个共同元素(dog 位于 list1 和 list2 中)，则返回 TRUE，否则返回 FALSE。

我认为我需要的第一件事是比较列表之间所有可能的排列，并且列表之间的比较是逐个元素的。我不确定这是最有效的方法。您能提出一个最终最有效的想法吗？

Answer 1

假设不应通过删除元素或对它们进行排序来更改给定列表(顺便说一句，复杂度为 O(nlogn))，那么您基本上需要一个函数作为实际解决方案的“构建 block ”。即，检查一个集合是否包含另一个集合中包含的任何元素的函数。

当然，这可以通过在第二个集合上使用Collection#contains来解决。但对于某些集合(特别是列表)，这需要 O(n)，并且检查的总体运行时间将为 O(n*n)。

为了避免这种情况，您可以创建一个包含第二个集合的所有元素的Set。对于 Set，contains 方法保证为 O(1)。

然后，可以使用Stream#anyMatch方便地完成实际检查:

containing.stream().anyMatch(e -> set.contains(e))

所以完整的例子可以是

import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class DuplicatesInLinkedLists
{
    public static void main(String[] args)
    {
        LinkedList<LinkedList<String>> lls =
            new LinkedList<LinkedList<String>>();
        LinkedList<String> list1 =
            new LinkedList<String>(Arrays.asList("dog", "cat", "snake"));
        LinkedList<String> list2 =
            new LinkedList<String>(Arrays.asList("donkey", "fox", "dog"));
        LinkedList<String> list3 =
            new LinkedList<String>(Arrays.asList("horse", "cat", "pig"));
        lls.add(list1);
        lls.add(list2);
        lls.add(list3);

        checkDuplicates(lls);
    }

    private static void checkDuplicates(
        List<? extends Collection<?>> collections)
    {
        for (int i = 0; i < collections.size(); i++)
        {
            for (int j = i + 1; j < collections.size(); j++)
            {
                Collection<?> ci = collections.get(i);
                Collection<?> cj = collections.get(j);
                boolean b = containsAny(ci, cj);
                System.out.println(
                    "Collection " + ci + " contains any of " + cj + ": " + b);
            }
        }
    }

    private static boolean containsAny(Collection<?> containing,
        Collection<?> contained)
    {
        Set<Object> set = new LinkedHashSet<Object>(contained);
        return containing.stream().anyMatch(e -> set.contains(e));
    }
}

<小时/>

旁注:您发布的代码几乎肯定在当前表单中没有意义。列表的声明和创建通常应该依赖于List:

List<List<String>> lists = new ArrayList<List<String>>();
lists.add(Arrays.asList("dog", "cat", "snake");
...

如果列表中的元素可以修改，那么你可以这样写

lists.add(new ArrayList<String>(Arrays.asList("dog", "cat", "snake"));

或者，类似地，使用 LinkedList 而不是 ArrayList，但对于所描绘的用例，我无法想象为什么应该有充分的理由故意使用 LinkedList 根本...