0

重複の可能性:
Java Compare Two Lists

順序付けられた 2 つの数字のシーケンスがある場合 (ここでは柔軟性が高く、データをリスト、セット、配列などに入れることができます)、一致を抽出する最も効率的な方法は何ですか? たとえば、私が持っている場合：

[1, 2, 4, 6, 9]そして[2, 3, 4]、私は戻りたい[2, 4]です。

これには明らかに多くの方法があります。どのような方法が最も効率的か興味があります。

4

6 に答える 6

10

リストごとに 1 つずつ、2 つのポインター (インデックス)。各リストの先頭から開始

一致するものを見つけるたびに、それを保存します。

一致しない場合は、現在のインデックスで最も低い値を持つリストを確認し、そのリストのインデックスを増やします。一致を確認します。リストのいずれかの最後に到達するまで、それを行います。

リストの合計のサイズに比例して実行されます (最悪の場合)。それをより良くする方法はありません。

于 2012-09-13T13:25:29.193 に答える
4

to セットの交差が必要ですか？Apache Commons のCollectionUtils.intersectionを使用できます。または、Guava Sets.intersection (ジェネリック) のものを使用することをお勧めします。

于 2012-09-13T13:24:17.193 に答える
2

これは、最良の選択と思われるintersection2 つのコレクションです。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

Set2 つのシーケンスをsに格納すると、 Set.retainAll()whichを使用できます。

指定されたコレクションに含まれるこのセットの要素のみを保持します (オプションの操作)。つまり、指定されたコレクションに含まれていないすべての要素をこのセットから削除します。指定されたコレクションもセットである場合、この操作はこのセットを効果的に変更し、その値が 2 つのセットの交差になるようにします。

例えば：

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

として 2 つのリストを作成し、java.util.Set1 つのセットを一時変数にコピーして、retainAll(<otherSet>)この一時セットを呼び出します。次に、一時的なセットは、2 つのセットの交点から離れます。

于 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 に答える