4

次の問題があります。順序付けされていない2つのリストで同じ要素のペアを見つける必要があります。これらの2つのリストについては、「ほぼ等しい」ということです。たとえば、特定の要素のみがいくつかのインデックスによってシフトされます（これらのオブジェクトは整数ではなく、この例では整数を使用しています）。

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

私の最初の試みは、両方のリストを反復処理し、各オブジェクトの一意のキーに基づいて2つのHashMapを生成することです。次に、2回目のパスで、両方のマップから要素をプルします。これによりO(2N)、空間と時間が得られます。

私は別のアプローチを考えていました。両方のリストの現在の要素へのポインターと、各リストのcurrentlyUnmatchedセットを保持します。擬似コードは次の種類のsthになります。

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）である必要があります。とにかく、お返事をお待ちしております。

編集：一致/不一致として見つけたオブジェクトに対して操作（複数の操作でも）を実行する必要があるため、2つのオブジェクトリストの設定された共通部分を単純に返すことはできません

4

3 に答える 3

1

一致/不一致として見つかったオブジェクトに対して操作 (複数の操作も) を実行する必要があるため、単純に 2 つのオブジェクト リストの積集合を返すことはできません。

一致しないオブジェクトのセットを維持できます。これは、任意の時点でスワップされた要素の最大数が M である空間で O(M) になります。N が要素の数である場合、時間は O(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 に答える