文字列が与えられた場合、どのような効率的な方法がありますか
- その中の N 番目に低い文字を返します (ASCII に関して)?
- その中の N 番目のローセット char* s * を返しますか?
ピボットが N 番目の位置にある場合、N 回の反復を挿入ソートでソートするか、クイックソートでソートすることを考えましたが、時間の複雑さを分析するのに問題がありました。他にもっと効率的な方法はありますか？
文字列ではなく、小数のリストだった場合の解決策は何ですか?
質問する
116 次
1 に答える
1
文字列がASCIIの場合、カウントソートスタイルのアルゴリズムを使用してそれを行うことができます。256個のカウンターの配列を作成し、文字列を調べて、文字列内にある各文字のコードのカウンターをインクリメントします。次に、配列をゼロからウォークし、これまでに見たカウントを累積します。文字のカウンターを追加するchと、累積結果がクロスオーバーする場合、文字列が並べ替えられた場合、それが-番目の文字Nであることがわかります。このアルゴリズムはです。ここで、は文字列の文字数です。これは、カウントの配列を作成するのにかかる時間です。chnO(N)N
于 2013-01-20T21:42:12.577 に答える