algorithm - 同じ文字列をグループ化するための最適なアルゴリズムは何ですか?

Question

それぞれのソートアルゴリズムが仕事になりますが、それは OVERKILL です。

次のような入力の場合:

aa
cc
aa
bb
dd
bb
cc

次のようなものが必要です：

aa
aa
cc
cc
bb
bb
dd

各パターンの順序は必須ではありません。

この種の仕事にそのようなアルゴリズムはありますか?

Answer 1

ここでは単にハッシュテーブルを使用するか、より抽象的には連想配列を使用します。入力を繰り返し、まだ表示されていない場合は値（必要に応じてタグ）を1にしてハッシュテーブルに追加するか、ハッシュテーブルにすでに存在する場合はカウントを1ずつ増やします。

したがって、アルゴリズムは時間と空間の両方でO（n）であり、これは合理的に期待できる限り良好です。ハッシュテーブルは、アルゴリズムやソフトウェア設計のあらゆる場所に表示される非常に便利なデータ構造であるため、よく読んでおくことをお勧めします。

Answer 2

さて、私の頭のてっぺんから、各要素がいくつ存在するかをカウントするパスを実行し、それらを順番に投稿して新しい配列を作成することができます。これはO（n）になりますが、「インプレース」ではありません。

したがって：

// Make outputArrayCounter
// While inputArray has elements left:
//   if current element is new, add to outputArrayCounter
//   if current element has been seen before, increment a counter associated with that 
//   element.
// Part 2...
// Make outputArray
// create the appropriate number of elements as found in the outputArrayCounter for
// every different element type.

例を試してみましょう：

の元の入力がありaa bb aa cc cc dd ccます。

カウンターデバイスを作成し、入力をスキャンします。 aa、最初の要素が読み取られ、aaこれまでに遭遇したことがないため、これをカウンターデバイスに追加します。

カウンター装置：[(aa, 1)]

次に、次の入力を読んで続行しましょうbb。また、見つからず、追加されます。

カウンター装置：[(aa, 1), (bb, 1)]

aaもう一度ステップして、3番目の要素として読み取ります。これはデバイスにあるため、再度追加する代わりに、関連付けられているカウンターをaa1ずつインクリメントします。

カウンター装置：[(aa, 2), (bb, 1)]

続行して、エンドカウンターデバイスの状態を示します。

[(aa, 2), (bb, 1), (cc, 3), (dd, 1)]

次に、デバイスを調べて、同じ名前の各要素を一緒に、各要素の番号を何度も印刷します。（順序が重要な場合、それは、関連付けられたset-dictionaryを使用するか、順序を格納するある種のduple-arrayデバイスを使用するかを決定する実装の詳細です。これは言語固有ですが、理解できると確信しています。できません。ここにコメントしてください。解決策について説明します。）

print aa aa bb cc cc cc dd