2

整数値または整数範囲 (initial..final) を返すメソッドがあり、値がすべてばらばらかどうかを知りたいです。

次のソリューションよりも効率的なソリューションはありますか。

ArrayList<Integer> list = new ArrayList<Integer>();

// For single value
int value;
if(!list.contains(value))
    list.add(value);
else
    error("",null);

// Range
int initialValue,finalValue;
for(int i = initialValue; i <= finalValue; i++){
    if(!list.contains(i))
        list.add(i);
    else
        error("",null);
}
4

2 に答える 2

4

containsで値 ( ) を見つけることHashSetは、平均して一定時間の操作 (O(1)) であり、 a よりも優れていますList。ここで、containsは線形 (O(n)) です。したがって、リストが十分に大きい場合は、最初の行を次のように置き換える価値があります。

HashSet<Integer> list = new HashSet<Integer>();

この理由は、(ソートされていない) リストで値を見つけるには、目的のインデックスが見つかるまで、またはチェックするインデックスがなくなるまで、リスト内のすべてのインデックスをチェックする必要があるためです。平均して、値がリストにある場合は値を見つける前にリストの半分をチェックし、そうでない場合はリスト全体をチェックします。ハッシュ テーブルの場合、検索する値からインデックスを生成し、その 1 つのインデックスをチェックします (複数の をチェックする必要がある場合もありますが、適切に設計されたハッシュ テーブルでは一般的ではありません)。

また、Set を使用すると、各値が一意であることが保証されるため、既に存在する値を追加しようとすると、addが返さfalseれます。これを使用して、コードを少し単純化できます (注: List を使用する場合、これは機能しません。常に List を返すためですadd)true。

HashSet<Integer> list = new HashSet<Integer>();

int value;
if(!list.add(value))
    error("",null);
于 2012-12-10T17:08:08.593 に答える
2

範囲に関係する問題は、多くの場合、ツリーの使用に役立ちます。を使用してそれを行う方法は次のTreeSetとおりです。

public class DisjointChecker {

    private final NavigableSet<Integer> integers = new TreeSet<Integer>();

    public boolean check(int value) {
        return integers.add(value);
    }

    public boolean check(int from, int to) {
        NavigableSet<Integer> range = integers.subSet(from, true, to, true);
        if (range.isEmpty()) {
            addRange(from, to);
            return true;
        }
        else {
            return false;
        }
    }

    private void addRange(int from, int to) {
        for (int i = from; i <= to; ++i) {
            integers.add(i);
        }
    }

}

ここでは、エラー ハンドラーを呼び出すのではなく、checkメソッドは引数が以前のすべての引数と素であったかどうかを示すブール値を返します。範囲バージョンのセマンティクスは元のコードとは異なります。範囲がばらばらでない場合、要素は追加されませんが、元の場合、最初のばらばらでない要素より下の要素が追加されます。

いくつかの点について詳しく説明する必要があります。

  • Set::add追加によってセットが変更されたかどうかを示すブール値を返します。これをメソッドからの戻り値として使用できます。
  • NavigableSetあいまいですが標準的なサブインターフェースでSortedSetあり、悲しいことに無視されています。ただし、実際にはSortedSetここでわずかな変更を加えるだけでプレーンを使用できます。
  • NavigableSet::subSetメソッド ( など) は、指定された範囲に制限された基になるセットのSortedSet::subSet軽量ビューを返します。これにより、1 回の操作で範囲全体とのオーバーラップについてツリーをクエリする非常に効率的な方法が提供されます。
  • ここでのaddRange方法は非常に単純で、以前に n 個のアイテムを確認したチェッカーに m 個のアイテムを追加すると、O(m log n) で実行されます。O(m) で実行されるバージョンを作成するにはSortedSet、整数の範囲を記述した の実装を記述してから を使用しますSet::addAll。これの の実装には、線形時間でTreeSet他の を追加する特別なケースが含まれているためです。SortedSetその特別なセットの実装のコードは非常に単純ですが、多くのボイラープレートが含まれているため、読者の演習として残します。
于 2012-12-10T18:20:52.583 に答える