1

アイテムの配列リストがあり、それぞれに他のアイテムをパラメーターとして受け取るメソッドがあります。それらを繰り返さずに、可能なすべてのアイテムのペアでメソッドを確実に呼び出す最も効率的な方法は何でしょうか? (すべてのアイテムは一意であると見なすことができます)。

私のコード:

public boolean hasConflict (ArrayList<Item> items) {
    // For every possible pair of items...
        one = items.get(i);
        two = items.get(j);

        if ( one.conflictsWith (two)) {
            return true;
        }

    // If we reach the end of the list without finding a conflict
    return false;
}

編集：

one.conflictsWith (two)は と同じ値を返しますtwo.conflictsWith (one)。忘れてすみません。

このconflictsWithメソッドは、2 つの値が重複しているかどうかを比較していないため、残念ながら、ハッシュ テーブルを使用して並べ替えることができません。

4

3 に答える 3

3

呼び出す必要がない場合は簡単で、次のようにa.conflictsWith(b)しb.conflictsWith(a)て時間を節約できます。

for(int i = 0; i < list.size(); ++i) {
    final MyClass curr = list.get(i);
    for(int j = i + 1; j < list.size(); ++j) {
        curr.conflictsWith(list.get(j));
    }
}

つまり、 をループしてListから、2 番目のループでの残りをループしListます。

それ以外の場合は、すべてをループする必要があります

for(int i = 0; i < list.size(); ++i) {
    final MyClass curr = list.get(i);
    for(int j = 0; j < list.size(); ++j) {
        if(i != j) {
            curr.conflictsWith(list.get(j));
        }           
    }
}
于 2013-10-14T16:07:06.987 に答える
1

が対称である場合conflictsWith()、つまりone.conflictsWith(two) == two.conflictsWith(one)引数のすべてのペアに対して、次を使用します。

for (int i = 0; i < items.size(); i++)
{
    final Item one = items.get(i);
    for (int j = i + 1; j < items.size(); j++}
    {
        one.conflictsWith(items.get(j));
    }
}

対称でない場合は、さらに 2 倍チェックする必要があります。

for (int i = 0; i < items.size(); i++)
{
    final Item one = items.get(i);
    for (int j = 0; j < items.size(); j++} // only this line changed
    {
        one.conflictsWith(items.get(j));
    }
}

最後のものもチェックしone.conflictsWith(one)ます。それが問題になる場合は、 を使用して if (i != j)ください。

于 2013-10-14T16:07:46.773 に答える