📚 LeetCode - 88. Merge Sorted Array 2つのソート済み配列をマージする

🎯 問題概要

💡 LeetCode 88: Merge Sorted Array
2つの ソート済み配列 nums1 と nums2 を 1つにマージ し、nums1 に上書きする問題。

📝 入力

nums1 = [1,2,3,0,0,0]  # m = 3
nums2 = [2,5,6]  # n = 3

✅ 期待される出力

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

❗ ルール

• nums1 の後半 n 個は 空きスペース (0) → ここに nums2 をマージ！
• 新しい配列を作らずに、nums1 を直接変更すること！

---

🚀 3つのアプローチ

アプローチ	時間計算量	空間計算量	メリット	デメリット
Approach 1: ソートを使う	O((m+n) log(m+n))	O(1)	簡単で直感的	ソートの計算コストが高い
Approach 2: 前からマージ	O(m + n)	O(m)	ソートせず効率的にマージできる	nums1_copy の追加メモリを使う
Approach 3: 後ろからマージ（最適解） ✅	O(m + n)	O(1)	追加メモリ不要で最も効率的！	少し実装が難しい

---

📝 Approach 1: ソートを使う方法

💡 アイデア

1. nums2 の値を nums1 の空きスペース (0 の部分) にコピーする。
2. nums1 全体を ソート すればOK！

📌 実装

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # nums2 の要素を nums1 の空きスペースにコピー
        for i in range(n):
            nums1[m + i] = nums2[i]
        
        # nums1 をソート
        nums1.sort()

⚡ 計算量

• 時間計算量：O((m+n) log(m+n)) → .sort() のコストが高い
• 空間計算量：O(1) → 追加の配列を作らない

✅ メリット

✔ シンプルで直感的
✔ sort() を使うだけで簡単

❌ デメリット

✖ ソートの計算コストが高い（最適ではない）
✖ すでに ソート済み のリストなのに、無駄な処理をしている

---

📝 Approach 2: 2つのポインタを使って前からマージ

💡 アイデア

1. nums1_copy を作成し、最初の m 個をコピー
2. nums1_copy と nums2 を 2つのポインタを使って前からマージ
3. 小さい方の要素を nums1 に入れていく

📌 実装

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # nums1 の m 個の要素をコピー
        nums1_copy = nums1[:m]

        # 2つのポインタを用意
        p1 = 0  # nums1_copy のポインタ
        p2 = 0  # nums2 のポインタ

        # nums1 を上書きしながら統合する
        for p in range(n + m):
            if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]):
                nums1[p] = nums1_copy[p1]
                p1 += 1
            else:
                nums1[p] = nums2[p2]
                p2 += 1

⚡ 計算量

• 時間計算量：O(m + n) → 各要素を 1 回ずつ処理するだけ
• 空間計算量：O(m) → nums1_copy を作るためのメモリを使用

✅ メリット

✔ ソートしなくても速い！
✔ O(m + n) の高速処理

❌ デメリット

✖ nums1_copy を作るのでメモリを追加で使う（O(m)）

---

📝 Approach 3: 後ろからマージ（最適解！）

💡 アイデア

• nums1 の後ろにある 空きスペース (0) を活用！
• 後ろから大きい値を埋めていく ことで、メモリを追加で使わずに済む！

📌 実装

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # ポインタを3つ用意
        p1 = m - 1  # nums1 のデータ部分の最後の位置
        p2 = n - 1  # nums2 の最後の位置
        p = m + n - 1  # nums1 の最後のインデックス

        # 後ろから比較しながら埋める
        for p in range(m + n - 1, -1, -1):
            if p2 < 0:
                break
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1

✅ まとめ

• 最速 O(m + n)！
• 追加メモリを使わない（O(1）で済む！）

🙌 参考になったら、いいね＆シェアよろしく 🚀🔥