2

配列内の要素を頻度で並べ替えたい。

Input: 2 5 2 8 5 6 8 8 

Output: 8 8 8 2 2 5 5 6

これに対する1つの解決策は次のとおりです。

  • クイックソートまたはマージソートを使用して要素をソートします。O(nlogn)
  • ソートされた配列をスキャンして、要素とカウントの 2D 配列を作成します。の上）
  • カウントに従って、構築された 2D 配列を並べ替えます。O(nlogn)

私が読んだ他の考えられる方法の中で、1 つは二分探索木を使用し、もう 1 つはハッシュを使用します。

誰かが私にもっと良いアルゴリズムを提案できますか? 複雑さを軽減できないことはわかっています。しかし、私は非常に多くのトラバーサルを避けたいと思っています。

4

1 に答える 1

1

配列をソートせずに 1 回のパスを実行し、別の構造体で要素を見つけた回数を数えることができます。これは、見つける要素の範囲がわかっている場合は別の配列で実行でき、そうでない場合はハッシュ テーブルで実行できます。いずれにせよ、このプロセスは O(n) になります。次に、各要素が関連付けられている量を並べ替えパラメーターとして使用して、生成された 2 番目の構造 (カウントがある場所) の並べ替えを実行できます。この 2 番目のプロセスは、適切なアルゴリズムを選択した場合、O(nlogn) と言ったとおりです。

この 2 番目のフェーズでは、優先キューを使用してヒープ ソートを使用することをお勧めします。count 属性 (ステップ 1 で計算されたもの) によって要素を並べ替えるようにキューに指示し、要素を 1 つずつ追加するだけです。追加が完了すると、キューは既にソートされており、アルゴリズムは必要な複雑さを備えています。要素を取得するには、ポップを開始するだけです。

于 2013-06-24T07:23:04.023 に答える