文字のASCII値で文字列を並べ替える

ASCII 値

ASCII (American Standard Code for Information Interchange) は、コンピュータやインターネット上のテキスト データの最も一般的な文字エンコード形式です。標準の ASCII エンコード データでは、256 個の文字、数字、または特別な追加文字と制御コードが固有の値を持ちます。

＃＃＃問題文＃＃＃

この問題では、文字の ASCII 値に基づいて昇順でソートされた文字列を見つける必要があります。文字列はユーザ​​ーによって与えられた入力になります。この問題をどのように解決すべきかを見てみましょう。

いくつかの例を使ってこの問題を理解してみましょう。

入力

- s = "$%7wjk()"

出力

- "$%()7jkw"

説明

- 指定された文字列の文字の ASCII 値は次のとおりです - リーリー したがって、ASCII コード値の昇順に、文字列は "$%()7jkw" になります。

入力

- s = "#m 0f )nk"

出力

- "#)0fkmn"

説明

- 指定された文字列の文字の ASCII 値は次のとおりです -

リーリー したがって、ASCII コード値の昇順に、文字列は "#)0fkmn" になります。 問題の説明

問題を理解して解決策を見つけてみましょう。 ASCII テーブルには 256 文字があり、各文字は一意の値または位置を持っていることがわかっています。したがって、私たちの基本的な目標は、それに応じて文字を並べ替えることです。目的を達成するために使用できる外部関数を使用して、組み込みの並べ替え関数を使用できます。別のアプローチは、周波数ベクトルを作成し、その配列に各文字の周波数を格納することです。この周波数ベクトルと ASCII 値を使用して、新しい文字列を取得できます。

解決策 1 周波数ベクトルを使用する

＃＃＃アルゴリズム＃＃＃

ASCII テーブルの文字の総数は 256 であるため、サイズ 256 の周波数ベクトルを作成し、ベクトル全体をゼロで開始します

ループを実行して、指定された文字列の各文字の頻度を保存します
ここで、最初は空である出力文字列を定義します
別のループを実行して周波数ベクトルを反復処理します。これにより、i 番目の位置 Frequency_vector[i]

• を型キャストすることで出力文字列を取得できます。

出力文字列を最終結果として返します

• ＃＃＃例＃＃＃
以下は、上記のメソッドの C プログラム実装です:
• リーリー ＃＃＃出力＃＃＃ リーリー

  上記のコードの複雑さ

時間計算量 - O(n); n は文字列のサイズです。ここで、実際の時間計算量は O(n * 256) ですが、O(k * n) は O(n ) としてのみ考慮されるのに対し、256 は k と同様に定数として考慮できるため、O(n) とみなすことができます。 。

空間複雑度 - O(256); ここで占有される唯一の余分な空間は、サイズが 256 の周波数配列の空間であるためです。

解決策 2 組み込みの並べ替え機能を使用した解決策
• ＃＃＃アルゴリズム

• ソート関数で使用される外部比較関数を定義して、ASCII 値に従って文字をソートします。つまり、int 型の変換値が他の文字より小さい文字を返します。

次に、ヘルパー関数の組み込みソート関数を使用し、追加のパラメーター (比較関数) を使用して順序を正しく取得します。

ヘルパー関数を呼び出して、最終的な文字列出力を取得します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

  上記のコードの複雑さ李>

• 時間計算量: O(log(n)); ご存知のとおり、組み込みの並べ替え関数はコードの実行に O(n * log(n)) 時間を必要とします。この方法では、組み込みの並べ替え関数を使用し、その関数に基づいて文字を並べ替える追加の比較関数を使用します。

• 空間複雑度: O(1); 上記のコードでは、何らかのデータ構造に変数を格納していません。

＃＃＃結論は＃＃＃

この記事では、文字の ASCII 値に基づいて昇順で並べ替えられた文字列が検索されます。この問題は 2 つの方法で解決できます。まず、サイズ 256 (ASCII テーブルの文字数と同じ) の周波数ベクトルを作成し、各文字のすべての周波数を保存し、後ろから反復して目的の文字列を取得します。もう 1 つの方法は、sort 関数で渡される追加パラメータを利用して、組み込みのsort 関数を使用することです。

以上が文字のASCII値で文字列を並べ替えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。