1

私はたくさんのSortedSet<Long>構造を持っています：

1, 2, 5, 8, 10, 35, 77, ...
5, 9, 35, 50, 132, ...
2, 4, 8, 15, 17, 23, ...
... hundreds of thousands of such rows...

たとえば、後に続く番号を見つける必要があります50。この例（セットが3つしかない場合）では、です77。セットの数は膨大で、数十万です。どのアルゴリズムを提案しますか？

4

3 に答える 3

3

私が正しく理解していれば、ここに私の考えがあります：

Collection<SortedSet<Long>> sets = //...

long minAfter50 = Long.MAX_VALUE;
for (SortedSet<Long> set : sets) {
    final Long first = set.tailSet(51L).first();
    minAfter50 = Math.min(minAfter50, first);
}

これがアイデアです：

  • すべての入力セットを反復する
  • 50 以下のすべての値を切り取る
  • トリミングされたセットの最初の引数を取ります (50 より大きいことが保証されます)
  • 前のステップで収集された値から最小値を計算します

更新 ( @beerbajayコメントに基づく): SortedSet が実際に であるTreeSet場合、次のコードのパフォーマンスが向上する可能性があります。また、すべてのセットに 50 より大きい値があることを確認しています。

long minAfter50 = Long.MAX_VALUE;
for (TreeSet<Long> set : sets) {
    final Long higher = set.higher(50L);
    if (higher != null && higher < minAfter50) {
        minAfter50 = higher;
    }
}
于 2012-05-23T19:57:55.203 に答える
1

それが許可するすべての事前計算である場合、実行できる唯一のことは、各 SortedSet で tailSet を呼び出して、最小値を見つけることです。

追加のデータ構造を許可する場合、最も簡単な方法は、すべてのセットの和集合を追跡し、その上で tailSet を呼び出すだけです。

どちらもあなたが望む答えではないと思います。おそらく、あなたが持っている制約をよりよく説明できますか?

于 2012-05-23T20:01:50.317 に答える
0

set は二分探索木として実装され、最大数は常に最後になります。50 より大きい数字を簡単に検索できます。各セットで常に 50 より大きい最初の数字を取得します。

于 2012-05-23T20:01:33.193 に答える