0

Big O表記に関して、次の問題を解決する最良の方法は何ですか?

サイズ N の文字列配列を指定します。配列を反復処理し、配列内で最も多く繰り返された文字列を含む単一の文字列を返します。また、返される文字列は、配列内にあった回数だけ文字列を繰り返す必要があります。元。配列内で "Bob" が最も多く見つかった文字列であり、3 回見つかった場合、返される文字列は "BobBobBob" になります。

これを行う方法を考えて、HashMap などを使用して一意のキー値を強制し、文字列をキーとして保存し、頻度を値として保存することを考えていました。すべてが完了したら、値を比較するマップを反復処理する必要があります..

全体として、これにより O(n) + O(n) が得られます...もっと良い方法があるかどうか疑問に思っています

編集：

O(n) よりもうまくできないことは理解していますが、ここでの問題は、最初の配列を反復処理して HashMap を構築したら、次にハッシュマップを反復処理して、どのペアが最も高い値を持つかを判断する必要があることです。 be O(n) ..基本的に、リスト全体を1回だけ反復する必要がある場合にこれを行う方法はありますか

4

3 に答える 3

3

私の 2 セント: O(2n) は悪くありませんが、もっとうまくやれるかもしれません...

HashMap<String, Integer>その場で更新するWinnerText文字列とWinnerCount整数カウンターを使用できます。最後に、後者の 2 つを使用して結果文字列を作成すると、O(n) + O(1) が得られます。

于 2013-10-31T13:39:16.643 に答える
1

すべての配列をスローする必要があることは確かなので、次のような構造体またはクラスを作成するだけでよいと思います。

     class myString{
       public String str ;
       public int repetition ;
       public myString(String str){
             this.str = str ;
             repetition = 1 ;
       }
       public void increment(){
              repetition+=1;
       }
      }

これを使用して配列をスローし、新しいオブジェクトを作成し、既存のオブジェクトが見つかったらインクリメントします。最後に繰り返し値の大きいものを探している

于 2013-10-31T13:41:07.763 に答える
1

値を引き戻すためにリスト全体を循環する必要がある限り、O(n) よりも良くなることはありません。O(1) に近いものを引き戻す唯一の方法は、挿入中に最大値を計算する「最大」インスタンス変数を格納することです。

しかし、実際には、O(1) 挿入を O(n) 挿入と交換しているだけです。ただし、どちらをより頻繁に使用するかによっては、それでうまくいく場合があります。

より良い代替案 (オーバーヘッドが非常に重いですが) は、配列に値を挿入するときに、すべての合計カウントのハッシュマップを保存することです。次に、現在の合計を保持し、最大値を保存することは、O(n) よりも O(log n) に近い方がよいでしょう。

編集：

あなたが今求めていることを理解しています...値を二分探索ツリーに保存してみてください...データをデータ構造に追加するとデータがソートされ、そのデータ構造へのリコールはいずれかになります O(log n) トラバースされた get の場合、O(1) はルート (または最大値) を引き戻します。

于 2013-10-31T13:47:02.200 に答える