0

文字列の配列があり、それぞれの長さが異なります。例えば：

s[0] = "sSWXk"
s[1] = "qCk"
s[2] = "sOQQXPbk"
.
.
.
s[x] = "KVfdQk";

私もそれを与えられます

n = s[0].length() + s[1].length() + ... + s[x].length()

これらの文字列を辞書式順序で並べ替えるには、時間計算量O（n）の並べ替えアルゴリズムが必要です。

a < ab < b < bbc < c < ca

助言がありますか？時間計算量は、アルゴリズムの重要な要件です。

4

3 に答える 3

11

これに最適なトライと呼ばれるデータ構造があります。すべての単語をトライに挿入してから、トライに対してDFSを実行すると、単語が並べ替えられた順序で返されます。これには時間O（n）もかかります。ここで、nはすべての文字列の文字の総数です。

これは宿題だと思いますので、トライの実施方法の詳細は演習として残しておきます。:-)

お役に立てれば！

于 2012-06-12T19:38:29.953 に答える
1

私は同様のテストの質問をしました、それは私が間違っていました、しかしそれはそれ以来私を悩ませてきました。それで私はそれを調べ続けました、そして私は線形時間で結果を生み出すかもしれない他の2つの方法があると思います。1つは、文字列をベースが26の一連の整数として扱い、文字列を同じ長さにパディングした後、配列で基数ソートを使用することです（何らかの方法で、ストレージスペースを大幅に増やすことなくこれを行うための巧妙な方法があります） 、私は詳細を理解していません）。私は例を作成したりテストしたりしていないので、これがうまくいくとは断言できませんが、その原理は正しいようです。もう1つの方法は、バケットソートです。26個のリスト（バケット）へのポインターを含む26個の要素配列を使用します。各文字列を適切なバケットリンクリスト（「a」で始まるリスト）に並べ替えます 最初の配列要素などが指すリストに入れます。）次に、標準のO（n log n）メソッドを使用して各リストを並べ替えます。私は数学を完全には理解していませんが、コーメンの教科書「アルゴリズムの紹介」によると、このようにバケットソートを使用すると、線形の時間計算量になります。ただし、実際に大量のストレージを割り当てずに右パディングの要件を満たすことができる限り、スペースは基数スタイルの方法よりも大きくなるようです。

于 2020-10-09T15:46:59.200 に答える
0

これは宿題の問題なので、私はヒントを与えることしかできません。ヒント：カウントソートの修正バージョンを使用してください。charが8ビットであると仮定すると実用的です。

于 2015-10-10T13:56:34.577 に答える