0Pricing
Coding Interview Prep · レッスン

2 つのソート済みシーケンスをマージする

それぞれ 1 本のポインターで両方のリストを走査します

「2 つのソート済みシーケンスをマージする」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

マージ処理

2つのソート済みリストを、1つのソート済みリストにまとめます。このマージはマージソートの中心であり、さまざまな場面に登場します。🔗

2つの入力、それぞれに1つのポインタ

各リストに1つずつポインタを割り当て、どちらもインデックス0から開始します。後戻りせず、2つを一緒に前へ進めていきます。

i = 0
j = 0

常に小さいほうを取る

各ステップで2つの先頭要素を比較します。ソート順では小さいほうが次に来るため、それを結果に追加します。

選ばれた側を進める

値を取り出したら、その値があった側のポインタだけを進めます。もう一方のリストでは、最小の要素がまだ待っています。

if a[i] <= b[j]:
    out.append(a[i])
    i += 1
else:
    out.append(b[j])
    j += 1

メインループ

両方のリストに要素が残っている間、マージを続けます。どちらか一方が空になったら、比較する意味はなくなります。

while i < len(a) and j < len(b):
    # compare and append
    pass

残りを追加する

一方のリストが空になったら、もう一方はすでにソート済みです。そのため、残りの末尾を結果にそのまま追加します。

out.extend(a[i:])
out.extend(b[j:])

末尾をそのまま扱える理由

残った末尾はすでに順序どおりなので、これ以上比較する必要はありません。2つの extend 呼び出しのうち、一方は単に何も追加しません。

全体で線形時間

各要素を1回ずつ確認するため、サイズ n と m の2つのリストのマージには O(n + m) の時間がかかります。これ以上速くすることはできません。

安定性を保つ

値が等しい場合に <= を使うと、等しい要素を元の順序のまま保てます。追加のデータを一緒に扱う場合、この安定性が重要になります。

逆向きにもマージする

余分な領域のないバッファへマージするには、代わりに末尾から進み、最大の要素を最後に配置します。同じ考え方を逆向きにしたものです。

マージからソートへ

分割し、半分ずつ sort してからマージする、この再帰処理が マージソートです。ここまで学んだ2ポインタによるマージが、その中心的な仕組みです。

確認問題

それぞれに1つのポインタを置いて、2つのソート済みリストをマージしています。

まとめ

2つのソート済みリストを、それぞれ1つのポインタで走査し、常に先頭の小さいほうを取り出してから残りを追加します。O(n + m) で動作し、マージソートの基盤になります。🚀

よくある質問

「2 つのソート済みシーケンスをマージする」レッスンは無料ですか？

はい。「2 つのソート済みシーケンスをマージする」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「2 つのソート済みシーケンスをマージする」で何を学びますか？

それぞれ 1 本のポインターで両方のリストを走査します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「2 つのソート済みシーケンスをマージする」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. ソート済み配列での Two Pointers
  2. 指定された合計になるペアを見つける
  3. 重複をその場で削除する
  4. 2 つのソート済みシーケンスをマージする
← Coding Interview Prepに戻る