リンクリストに最も多く出現する文字

単一リンクされた文字リストが与えられました。私たちのタスクは、リンクされたリスト内で最も頻繁に出現する文字を出力することです。複数の文字が同じ回数出現する場合は、最後に出現した文字が出力されます。

単一リンク リストは、ノードで構成される線形データ構造です。各ノードにはデータと次のノードへのポインタが含まれます。各ノードに割り当てられたメモリは連続していないため、次のノードへのポインタには次のノードのメモリ アドレスが含まれます。

＃＃＃例＃＃＃

文字リンクのリストが与えられたと仮定します

例 1

入力: LL = a -> b -> c -> c -> c

出力: 最も一般的な文字は c です。

説明: 指定されたリンク リスト LL では、a が 1 回、b が 1 回、c が 3 回現れます。したがって、出力は c になります。

例 2

＃＃＃入力：＃＃＃

LL = x -> x -> y -> y -> z -> z

出力: 出現する最大の文字は z です。

説明: 指定されたリンク リスト LL では、x が 2 回出現し、y が 2 回出現し、z が 2 回出現します。 z が最後に現れるため、すべての出現は同じになり、出力は z になります。

ここでは 2 つの方法について説明します。次の部分を見てみましょう -

方法 1: 反復計算の頻度

このメソッドの考え方は、リンクされたリストを走査して各文字の頻度を計算し、最も高い頻度を持つ文字を見つけ、複数の文字が同じ頻度を持つ場合はその文字を出力して、最後の文字。

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

時間計算量

: O(N*N)、N はリンク リストのサイズです。

空間の複雑さ: O(1)

方法 2: カウント配列を使用する

このアプローチの考え方は、各文字の頻度を保存するカウントの配列を維持し、配列を反復処理して最も頻度の高い文字を見つけるというものです。複数の文字の頻度が同じ場合は、その文字を出力してから最後の文字を返します。

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

時間計算量

O(N)、N はリンク リストのサイズです。

空間複雑度: O(N)、N はリンク リストのサイズです。

＃＃＃結論は＃＃＃

ここでは、リンクされたリストに最も多く出現する文字を見つける方法について説明します。文字の最大出現数を見つけるために、2 つの方法について説明しました。最初の方法では、指定されたリンク リストの文字ごとに while ループを使用し、2 つ目の方法では、小文字ごとに for ループを使用してカウントを維持します。

以上がリンクリストに最も多く出現する文字の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。