1

助けが必要な問題が発生しました。キー（整数）と値（整数も）で構成されるデータセットがあるとします。キーの値が与えられた場合、それが属する最小のキー範囲を見つけて（つまり、最も近い大きいキーと小さいキーを見つけて）、補間によって一致する値を返すことができる必要があります。どちらの方法でこれを最速で実行できるのか疑問に思いました（スペースの複雑さはそれほど重要ではありません）。また、削除は関係なく、すべての値は起動時に指定されます（起動後に追加される値はなくなると想定される場合があります）。私は挿入よりも検索時間に重点を置いています。

最も基本的な解決策は、ソートされたキーの配列を保持し、その上でバイナリ検索を使用することです。入力キーが見つかるか、入力キーよりも大きい2つの隣接する要素が見つかるまでです。このオプションは、挿入と検索にO（log n）を取ります。もっといいものはないかと思っていました。

ありがとう！

4

1 に答える 1

2

TreeMapなどのNavigableMapを使用します。

NavigableMap<Integer, Integer> map = new TreeMap<>();
map.put(1, 10);
map.put(0, -10);
map.put(5, 25);
map.put(3, 20);

// find the value below.
int key = 2;
Map.Entry<Integer, Integer> entry1 = map.floorEntry(key);
Map.Entry<Integer, Integer> entry2 = map.ceilingEntry(key);
System.out.println(key + " is between " + entry1 + " and " + entry2);

プリント

2 is between 1=10 and 3=20

挿入、更新、ルックアップ、および削除には、次のような時間計算量があります。O(log N)

于 2012-08-22T13:55:14.000 に答える