3

BST で最も頻繁に発生する要素を見つけるにはどうすればよいでしょうか? ハッシュマップを使って実装することを考えました。簡単な方法はありますか？

4

4 に答える 4

7

この問題は、並べ替えられた配列で最も頻繁に使用される要素を見つけることと同じです。同じアルゴリズムが適用されます。

  • カウンターをゼロからスタート
  • 現在の要素が前の要素と等しい間、カウンターをインクリメントします
  • 別の要素を見つけたら、カウンターを現在のベスト ランと比較します。必要に応じて交換
  • 次の要素に進む

唯一の違いは、ループを使用した配列トラバーサルの代わりに、再帰関数を使用してツリー トラバーサルを行うことです。どちらの場合も、アルゴリズムはツリー内の要素の数に関して時間的に線形です。ツリーのバランスが取れている場合、アルゴリズムはO(LogN)呼び出しスタックにスペースを必要とします。

于 2013-07-13T13:08:43.437 に答える
2

複数の方法で実行できます-

  1. BSTのインオーダー トラバーサルを実行します。これにより、要素のソートされたリストが得られます。線形トラバーサルを実行して、最も繰り返される要素を見つけます。time O(n) space O(n)
  2. あなたが言ったようにハッシュテーブル。BSTのDFS 走査のいずれかを実行します。count を 1 に設定して、各要素をハッシュテーブルに挿入します。要素が既に存在する場合は、count+1 を増やします。次に、ハッシュテーブルをトラバーサルして、頻繁に発生する要素を見つけます。最悪の場合の時間O(n)とスペースO(n)ですが、実際には、データセットに多くの重複がある場合、このアプローチはより少ないスペースで済みます。
于 2013-07-13T13:06:35.600 に答える
0

それはそれを行うための最もクリーンな方法です：

  • 値をその出現回数にマップするハッシュマップを初期化します。
  • BST を順番に繰り返します。
    • ハッシュ[ノード.値] += 1

その場で行うことができます（O(1)追加のメモリの複雑さ）：

2つO(1)の変数を保持して、最大出現数と要素を示し、ツリーを順番に反復して、増加する方法を約束し、要素の最大出現数を更新します。

curmax = 0
maxnode = null
for each node in BST.inorder():
    if next.value == node.value:
        max ++
    else:
        max = 1
    if max > curmax:
        curmax  = max
        maxnode = node
于 2013-07-13T13:08:18.463 に答える