ホームページ  >  記事  >  バックエンド開発  >  C++ プログラム: リンク リスト内の重複ノードをコピーに置き換えます

C++ プログラム: リンク リスト内の重複ノードをコピーに置き換えます

王林
王林転載
2023-08-27 08:41:141154ブラウズ

C++ プログラム: リンク リスト内の重複ノードをコピーに置き換えます

この記事では、重複のある 1 から n までの要素を含むリンク リストが与えられます。要素 1 ~ n は、[1..n] 内に常に重複して存在します。繰り返される各要素を n 1、n 2 などに置き換える必要があります。

例を考えてみましょう

1→2→2→4→5→3→6→6

次の n = 42。したがって、各重複は n 1、n 2 などに置き換えられます。次の 42 は 47 に置き換えられ、次の 46 は 48 に置き換えられ、最初のインスタンスはそのまま残ります。

まず、以下に示すように、main メソッドでバイナリ ツリーを構築する必要があります -

リーリー

ノードは次のようになります;

1→2→7→4→5→3→6→8

これまで見てきたように、n の開始値を見つけるには、表示される要素を追跡する必要があります。また、値を置き換えるためにどの要素が繰り返されるかを決定するメカニズムも必要です。

すぐに思い浮かぶ提案されたデータ構造が特定されました。リンクされたリストを反復処理して、要素をコレクションにプッシュできます。セットから要素をプッシュした後、セットはソートされたデータ構造であるため、リンクされたリストで使用可能な最大の要素である最後の要素を見つけることができます。

リンク リストの 2 回目の走査では、セットをハッシュとして使用できます。コレクション内のすべての要素を検索します。2 つの状況が発生する可能性があります。

  • コレクション内で要素を見つけて、それをコレクションから削除してマークします。

  • セット内に要素が見つかりませんでした。つまり、オプション 1 から要素を確認したので、それを次の n に置き換えます。

###例###

リンク リスト内の重複した値を持つノードを置き換えるには、以下の C プログラムに従ってください。 C の実装では、コレクション データ構造を利用してリンク リストを走査するため、重複要素の検索が容易になります。

リーリー ###出力### リーリー ###結論は###

ハッシュの概念を使用し、一連のデータ構造を利用してリンク リスト内の最大の要素を見つけました。また、map または unowned_map をハッシュとして使用することもできます。

以上がC++ プログラム: リンク リスト内の重複ノードをコピーに置き換えますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事はtutorialspoint.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。