4

我有以下问题：我需要在两个无序的列表中找到相同元素对。关于这两个列表的事情是它们“大致相等” - 只有某些元素被移动了一些索引，例如（注意，这些对象不是整数，我在这个例子中只是使用整数）：

[1,2,3,5,4,8,6,7,10,9]
[1,2,3,4,5,6,7,8,9,10]

我的第一次尝试是遍历这两个列表并根据每个对象的某个唯一键生成两个 HashMap。然后，在第二遍时，我会简单地从两个地图中提取元素。这产生O(2N)了空间和时间。

我正在考虑一种不同的方法：我们将在两个列表中保留指向当前元素的指针，以及为每个列表设置 currentUnmatched 。伪代码将是以下类型：

while(elements to process)
    elem1 = list1.get(index1)
    elem2 = list2.get(index2)
    if(elem1 == elem2){ //do work
         ... index1++; 
             index2++;
    }
    else{
        //Move index of the list that has no unamtched elems
        if(firstListUnmatched.size() ==0){
            //Didn't find it also in the other list so we save for later 
            if(secondListUnamtched.remove(elem1) != true)
                firstListUnmatched.insert(elem1)
            index1++
        }
        else { // same but with other index}
    }

以上可能不起作用......我只是想大致了解您对这种方法的看法。基本上，这会在每个列表的一侧维护一个哈希集，其大小 << 问题大小。对于少量错位元素和小的“间隙”，这应该是~O(N)。无论如何，我期待着您的回复。

编辑：我不能简单地返回两个对象列表的集合交集，因为我需要对我发现匹配/不匹配的对象执行操作（甚至多个操作）

4

3 回答 3

1

我不能简单地返回两个对象列表的集合交集，因为我需要对我找到的匹配/不匹配的对象执行操作（甚至多个操作）

您可以维护一组不匹配的对象。这将是空间中的 O(M)，其中 M 是任意点交换元素的最大数量。时间为 O(N)，其中 N 是元素的数量。

interface Listener<T> {
    void matched(T t1);
    void onlyIn1(T t1);
    void onlyIn2(T t2);
}

public static <T> void compare(List<T> list1, List<T> list2, Listener<T> tListener) {
    Set<T> onlyIn1 = new HashSet<T>();
    Set<T> onlyIn2 = new HashSet<T>();
    for (int i = 0; i < list1.size(); i++) {
        T t1 = list1.get(i);
        T t2 = list2.get(i);
        if (t1.equals(t2)) {
            tListener.matched(t1);
            continue;
        }
        if (onlyIn2.remove(t1)) 
            tListener.matched(t1);
         else 
            onlyIn1.add(t1);
        if (!onlyIn1.remove(t2))
            onlyIn2.add(t2);
    }
    for (T t1 : onlyIn1)
        tListener.onlyIn1(t1);
    for (T t2 : onlyIn2)
        tListener.onlyIn2(t2);
}
于 2012-10-09T11:30:46.723 回答
0

如果我正确理解了您的问题，您可以使用Collection.retainAll然后遍历保留的集合并执行您必须做的事情。

list2.retainAll(list1);
于 2012-10-09T11:41:14.493 回答
0

所有基于地图的方法充其量都是 O(n log(n))，因为创建地图是一种插入排序。效果是对两者进行插入排序，然后将它们进行比较，这将达到预期效果。

如果列表几乎开始排序，排序步骤不应该像平均情况一样长，并且将按 O(n log(n)) 进行缩放，所以只需对两者进行排序并进行比较。这使您可以单步执行并根据需要对匹配或不匹配的项目执行操作。

于 2012-10-09T12:01:16.637 回答