sorting - ソート配列アルゴリズム - 重複値

Question

値が重複する整数配列サイズ N があり、値の範囲がわかりません。この配列には n/logn 異なる値があり、残りはすべて重複しています。

O(n) の時間の複雑さと O(n/logn) のメモリの複雑さで並べ替える方法はありますか?

Answer 1

キーと値のペアを保持するだけ

 for(i=0;i<n;i++)
    {
int key = a[i];
//       if value is in map increase vale of this key
// else add key with value 1 
    } 

マージソートを使用して、このマップデータを出力配列に書き込み、これで問題が解決することを願っています..

Answer 2

たとえば、マージソートは、O(n) 空間の複雑さを持つ O(n*lg(n)) 時間アルゴリズムです。

ハッシュ マップを使用して、n/lg(n) 個の一意のアイテムを独自の配列に抽出し、各アイテムの発生回数を記録できます。これは (予想される) O(n) 時間と O(n/lg(n)) 空間です。これで、次の新しい配列で Mergesort を実行できます。

O(x*lg(x)) 時間 x=n/lg(n) ==
O(n/lg(n) * lg(n/lg(n))) ==
O(n/lg(n) * [lg(n) - lg(lg(n))]) ==
O(n - n*lg(lg(n))/lg(n))
<= O(n) 時間

と

O(x) 空間 x=n/lg(n) ==
O(n/lg(n)) 空間

最後に、ハッシュ マップに記載されている重複数に基づいて要素を複製することにより、順序付けられた配列を最終結果に展開します。