💬

88. Merge Sorted Array

に公開
PHP
LeetCode
tech

2つの整数配列 nums1 と nums2 が与えられます。これらは非減少順（昇順）に並んでおり、それぞれ m と n という整数が与えられます。m は nums1 に含まれる要素数、n は nums2 に含まれる要素数を表します。

nums1 と nums2 を1つの配列にマージし、それを非減少順に並べてください。

最終的なソート済み配列は関数から返すのではなく、nums1 配列内に格納してください。
このために、nums1 の長さは m + n に設定されており、先頭の m 要素がマージ対象、残りの n 要素は 0 で初期化されていて無視してよい部分です。nums2 の長さは n です。

例1:

入力:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

出力:
[1,2,2,3,5,6]

説明:
マージ対象の配列は [1,2,3] と [2,5,6] です。
マージ結果は [1,2,2,3,5,6] になります（下線の部分は元の nums1 からの要素）。

例2:

入力:
nums1 = [1], m = 1
nums2 = [], n = 0

出力:
[1]

説明:
マージ対象は [1] と []。
結果は [1]。

例3:

入力:
nums1 = [0], m = 0
nums2 = [1], n = 1

出力:
[1]

説明:
マージ対象は [] と [1]。
結果は [1]。
ここでは m = 0 のため、nums1 には実際の要素は含まれておらず、0 はマージ結果を格納するための空き領域です。

1. 後ろからマージしていくことで上書きを防ぐ

  • 通常前からマージしようとすると、nums1 の既存の値を上書きしてしまう問題が起きます。
  • でも後ろから書いていけば、未処理のデータはそのまま残っているので、安全に処理できる。
nums1: [1,2,3,0,0,0]
               ↑ ここから埋めていく

2. while ($j >= 0)：nums2 だけ見ればOK

  • マージ処理の条件は「nums2 の要素が残っているか」だけで十分。
  • nums1 はすでに元のデータが入ってるから、必要に応じて右へコピーすればいい。
  • $i < 0 のときは nums1 にデータが残ってない＝強制的に nums2 をコピーすべき状態
if ($i < 0 || $nums1[$i] < $nums2[$j]) {
    $nums1[$mergeIndex] = $nums2[$j];
    $j--;
}

3. in-placeかつO(m + n)時間、O(1)空間の効率性

  • ソート済みの2配列をO(m + n)でマージするのは最適解の手法。
  • 追加メモリを使わず、メモリ効率も非常に良いのが魅力。

Discussion