アルゴリズム概要

O(m+n)
時間計算量
O(1)
追加空間
3 Pointers
使用ポインタ数
In-place
操作種別

問題設定

ソート済み配列 nums1（有効要素 m 個、末尾 n 個はゼロ埋め）と nums2（n 個）を nums1 にインプレースでマージし、非減少順に並べる。

入力

nums1 = [1,2,3,0,0,0], m = 3

nums2 = [2,5,6], n = 3

出力

[1, 2, 2, 3, 5, 6]

核心アイデア

  • ✓ 後ろから書く：前から書くと有効要素を上書きするため、末尾 k = m+n-1 から書き込む
  • ✓ 不変条件 k ≥ i：書き込みポインタが読み取りポインタを常に追い越さないため、未処理要素を上書きしない
  • ✓ 残余は nums2 のみ：nums1 の残余は既に正しい位置にある。nums2 の残りのみコピーする

ステップバイステップ解説

実装コード

処理フローチャート

開始 ポインタを初期化 i = m-1 | j = n-1 | k = m+n-1 i ≥ 0 かつ j ≥ 0 ? YES NO 比較・書き込み if nums1[i] ≥ nums2[j]: nums1[k] = nums1[i]; i-- else: nums1[k] = nums2[j]; j-- k-- ループバック nums2 残余コピー while j >= 0: nums1[k] = nums2[j]; k--; j-- 終了
フロー説明
1. 初期化：i = m-1（nums1 有効末尾）、j = n-1（nums2 末尾）、k = m+n-1（書き込み末尾）
2. ループ判定（黄ダイヤ）：i≥0 かつ j≥0 の間ループ。どちらかが尽きたら NO で残余処理へ
3. 比較・書き込み：nums1[i] と nums2[j] を比較し大きい方を nums1[k] に書き込み、対応するポインタを減算
4. k-- 後に紫破線でループ条件へ戻る（不変条件 k ≥ i を維持）
5. 残余コピー：nums2 が残っていれば残りの要素をコピーする

計算量分析

アプローチ 時間計算量 空間計算量 備考
後ろから 3 ポインタ ✅ O(m+n) O(1) 最適解。追加アロケーションなし
コピー後 .sort() O((m+n) log(m+n)) O(m+n) 実装最短だが計算量で劣る
一時バッファ使用 O(m+n) O(m) 前からマージ可能だが空間を消費
heapq.merge O(m+n) O(m+n) 一時リスト生成あり
不変条件の証明： 初期値 k - i = n ≥ 0。 各イテレーションで k は必ず 1 減少し、i か j のどちらかも 1 減少する。 i 減少時は k - i が不変、j 減少時は k - i が 1 増加。 よって k ≥ i が常に成立し、未処理の nums1 要素を上書きしない。