1

任意のコレクションに格納できる順序付けられた数値 {1、2、4、10、14、20、21、24、29、30} の静的セットがあります。新しい数値が渡された場合、新しい数値に最も近い、より大きな数値を見つけることができる必要があります。

例: 注文番号の静的セットが {1、2、4、10、14、20、21、24、29、30} の場合。渡される数値は 23 で、最も近い大きい数値は 24 です。

静的な数値を配列に格納することを考えました。配列をループしてから最も近い数を見つけようとしますが、この解決策は O(n) です。より速い方法はありますか？

4

3 に答える 3

3

Java 1.6 には、NavigableSetインターフェイスがあります。TreeSet と ConcurrentSkipListSet の両方がこのインターフェイスを実装します。これは SortedSet のサブインターフェースであり、SortedSet を置き換えることを目的としています。

これで、この NavigableSet にコレクションができました。これで2 つのメソッドが用意されました。floorとCeilingは、それぞれ引数よりも小さいか大きい要素を返します。または、引数がある場合は equal を返し、そのような要素がない場合は null を返します。

これにより、次の行に沿って何かを行うことができます。

int closest(int arg) {
    Integer ceil = set.ceiling(arg);
    Integer floor = set.floor(arg);

    if(ceil == null) { return floor; }
    if(floor == null) { return ceil; }

    int cdiff = ceil - arg;
    int fdiff = arg - floor;

    if(cdiff < fdiff) { return ceil; }
    else { return floor; }
}

小さいサイズの配列の場合、この実装と他の実装の速度の違いはほとんどないことに注意してください。

大量の数値セットを扱っている場合は、二重にリンクされたボトム レベルを使用して、独自のスキップ リスト(きちんとしたデータ構造) を実装することを検討することをお勧めします。次に、値がない場合に値があるべき場所に到達し、下のレベルを簡単に上下に移動して、次に高い数値と低い数値を取得できます。

于 2013-10-27T03:14:16.917 に答える
3

整数の配列がソートされていると仮定すると、 を使用できますArrays.binarySearch(array, key)。

呼び出しの結果はbinarySearch、配列内のキーのオフセットまたは「挿入ポイント」です。つまり、キーを挿入する必要があるオフセットです。挿入ポイント (負の数値で表される) を取得すると、それを使用して、配列内の次に大きい数値または次に小さい数値を識別できます。(「挿入ポイント」の正確な意味と表現については、javadoc で説明されています。)

この手順の複雑さはO(logN).

これは、リストでラップする前に をCollections.binarySearchに変換する必要があるため、を使用するよりも高速です。また、 から始めた場合は、任意のオブジェクト配列で機能する の代替オーバーロードがあります。int[]Integer[]Integer[]Arrays.binarySearch

TreeSetまた、入力配列からを作成するよりも高速です。ただし、TreeSet には、セットを作成すると、更新が安価になるという利点があります...配列または配列リストベースの表現と比較して。(ただし、更新は上記の要件の一部ではありません。)

于 2013-10-27T02:33:40.163 に答える
0

順序付きリストがある場合は、それを List に配置してCollections.binarySearch(list, valueToCheck)を呼び出すだけです。

戻りインデックスが負の場合は、対応する正のインデックスに変換し、その数値が渡された数値よりも大きいことを確認する必要があります (正の数値に変換する必要があります。リストの最後の番号)。

于 2013-10-27T02:01:16.853 に答える