0

私はフォーラムに不慣れですが、ガイドラインを読み、重複をチェックしました（これは私が見つけた最も近いものです:(単語ストリームで最も頻繁な単語を見つける方法は？）しかし、これは51％以上発生する番号を検索しますすでに存在する場合は、重複を指摘してください。

だから私の質問は数字の流れを与えられ、最も頻繁に発生する数字を見つけます。例：2,3,4,2,5：Ans = 2これは簡単ですが、新しい番号を削除して追加できるとどうなりますか。例：2,3,5,3,4,2,2：最大= 2 Delete（2）：最大= 2; Delete（2）：最大=3..。

更新がO（log n）で、最大値がO（1）になるように、ヒープ内の各ノードへのポインターを含むハッシュテーブルとともに最大ヒープについて考えました。より良い解決策はありますか？

4

1 に答える 1

1

主に高速更新に関心がある場合は、キー（整数）を値（各整数の現在の出現回数）に関連付ける任意のデータ構造を使用できます。整数の「追加」と「削除」は、出現回数をインクリメントおよびデクリメントすることで簡単に処理されます。

二分木に基づくコンテナの場合、操作はO（logN）になりますが、ハッシュテーブルの場合はO（1）になります。いずれの場合も、「最大値を見つける」はO（N）になります。

あなたが主に速い「最大値を見つける」ことに興味があるなら、あなたの提案された解決策はそれが得るのと同じくらい良いです。

于 2013-02-25T12:31:49.983 に答える