2

何かのソートされたリスト（a、a、b、c、c）が与えられた

aリストに2回、1回、2回存在するbことを認識する最も効率的な方法は何でしょうcか。

カウントのマップを作成することは別として。これよりもうまくやれるでしょうか？

            if (map.containsKey(key)) {
                map.put(key, map.get(key) + 1);
            } else {
                map.put(key, 1);
            }

最終的な目標は、リストを反復処理し、任意の時点でキーが以前に何回表示されたかを知ることです。物事を地図に入れることは、私たちが本当に必要としないステップのように思えます。

4

2 に答える 2

3

私はGuavaMultisetの実装を使用します-おそらく。これにより、反復ごとに/を実行する必要がなくなります。アイテムを追加したときにアイテムがすでに存在する場合は、カウントが増加するだけです。を使用するのと少し似ています。HashMultisetputgetHashMap<Foo, AtomicInteger>

詳細については、GuavaユーザーガイドのエントリをMultiset参照してください。

于 2012-09-19T21:04:38.450 に答える
1

あなたのメソッドは、各反復で、

  • containsKeyの1つのルックアップ
  • getの1つのルックアップ
  • Integerからintへの1つのボックス化解除
  • intからIntegerへの1つのボクシング
  • ワンプット

現在の要素を前の要素と単純に比較し、等しい場合はカウントをインクリメントし、そうでない場合はカウントを設定します（そしてカウンターを1にリセットします）。

ただし、アルゴリズムを保持している場合でも、getを使用して結果をnullと比較すると、少なくとも不要なルックアップを回避できます。

于 2012-09-19T21:05:31.687 に答える