[LeetCode解法] 88. Merge Sorted Array

問題の説明

LeetCode 88. Merge Sorted Array

与えられた2つの昇順リストを昇順にマージする問題です。 ただし、条件があり、nums1の配列をin-place方式でソートする必要があります。

解法

アプローチ

1) 最初に入力として与えられたnums1の0,0..の部分にnums2の配列をコピーします。 2) コピーした配列をsort()関数を使用してソートします。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[m:] = nums2[:] # [1,2,3,2,5,6],

        nums1.sort() # [1,2,3,2,5,6] #Tim sort O(nlogn)

上記解法の時間複雑度と空間複雑度は次の通りです。

• 時間複雑度: O((m+n)log(m+n))
  • Python3のsort()関数はTim sortを使用しており、O(nlogn)の時間複雑度を持ちます。nums1の数mとnums2の数を合計したm+nの時間複雑度となります。
• 空間複雑度: O(1)
  • 追加の空間は使用されません。