0

可能重复：
Java 比较两个列表

如果我有两个有序的数字序列（我在这里有很大的灵活性，并且可以将我的数据放在列表、集合、数组等中），那么提取匹配项最有效的方法是什么？例如，如果我有：

[1, 2, 4, 6, 9]而且[2, 3, 4]，我想回来[2, 4]。

显然有很多方法可以解决这个问题。我很好奇最有效的方法是什么。

4

6 回答 6

10

两个指针（索引），每个列表一个。从每个列表的开头开始

每当您找到匹配项时，将其存储起来。

如果没有匹配项，请检查哪个列表在当前索引中具有最低值并增加该列表的索引。检查匹配。这样做直到您到达列表之一的末尾。

与列表总和的大小成线性关系（更糟糕的情况）。没有办法做得更好。

于 2012-09-13T13:25:29.193 回答
4

所以你想要 to 集的交集？您可以使用apache commons 中的CollectionUtils.intersection。或者更好的是，来自 Guava Sets.intersection（通用）的那个。

于 2012-09-13T13:24:17.193 回答
2

这是intersection两个系列，我想Set这将是最好的选择。

请参阅Collection.retainAll()

仅保留此集合中包含在指定集合中的元素（可选操作）。换句话说，从这个集合中移除所有不包含在指定集合中的元素。

一种更有效的方法是

public static void main(String[] args) {
    int[] firstArray = { 1, 3, 5, 8, 10 };
    int[] secondArary = { 3, 8 };
    //Arrays.sort(firstArray); If arrays needs to be sorted
    //Arrays.sort(secondArary);
    System.out.println(Arrays
            .toString(intersection(firstArray, secondArary)));

}

private static Integer[] intersection(int firstArray[], int secondArary[]) {
    int i = 0;
    int j = 0;
    ArrayList<Integer> list = new ArrayList<Integer>();
    while (i < firstArray.length && j < secondArary.length) {
        if (firstArray[i] < secondArary[j])
            i++;// Increase I move to next element
        else if (secondArary[j] < firstArray[i])
            j++;// Increase J move to next element
        else {
            list.add(secondArary[j++]);
            i++;// If same increase I & J both
        }
    }
    return list.toArray(new Integer[0]);
}
于 2012-09-13T13:24:26.637 回答
2

如果将两个序列存储到Sets 中，则可以使用Set.retainAll()which：

仅保留此集合中包含在指定集合中的元素（可选操作）。换句话说，从这个集合中移除所有不包含在指定集合中的元素。如果指定的集合也是一个集合，则此操作有效地修改此集合，使其值是两个集合的交集。

例如：

Set<Integer> s1 = new TreeSet<Integer>();
s1.add(1);
s1.add(2);
s1.add(6);

Set<Integer> s2 = new TreeSet<Integer>();
s2.add(2);
s2.add(6);

s2.retainAll(s1);

for (Integer i: s2)
{
    System.out.println(i);
}

输出：

2
6
于 2012-09-13T13:24:51.157 回答
1

我会将这两个列表创建为java.util.Set，将一组复制到一个临时变量并调用retainAll(<otherSet>)这个临时集。然后临时集合将留在两个集合的交集处。

于 2012-09-13T13:24:57.320 回答
0

我会使用TreeLists并执行以下操作：

TreeList<Integer> list1 = ...
TreeList<Integer> list2 = ...

Iterable<Integer> result = Iterables.filter(list1, Predicates.in(list2));

这使用 Guava 的 Iterables 和 Predicates。

于 2012-09-13T13:28:05.570 回答