Merged Sorted Array[LeetCode/Python3/Easy]

 

題目

給定兩個非遞減排序的整數數組nums1和nums2，以及兩個整數m和n，分別表示nums1和nums2中的元素數量。

將nums2合併到nums1中，並且是按照非遞減排序的方式。

最終排序好的數組不應該由函數返回，而應該是被存儲在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只是為了確保合併結果可以放入nums1中。

限制:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• 109 <= nums1[i], nums2[j] <= 109
• *跟進問題：**能否設計一個時間複雜度為O(m+n)的算法？

我的答案

直覺答案

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        j=0
        i=0
        while i < m+n:
            if n ==0 or j==n:
                return nums1
            elif i==m+j:
                nums1[i]=nums2[j]
                j+=1   
            elif nums1[i] >= nums2[j]:
                nums1.insert(i, nums2[j])
                nums1.pop()
                j+=1
            i+=1
        
        return nums1

我的直覺就是直接從nums1的前面開始安插nums2的數值，然後每安插一個nums2的數值後，把nums1後方的0移掉

有趣的解答

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        for i in range(0,n):
            nums1[m+i] = nums2[i]
        nums1.sort()

這答案實在太有趣了！簡潔而暴力😂直接把nums2的數值插入進去nums1，然後直接用python內建的sort function！

稍微去找了一下python 內建的sort function是採用 Timsort algorithm。

簡單來說是去找數據內有序的subset，然後以這個有序的subset進行merge sort，在最差的情況下，他的執行複雜度是 O(nlogn) 。

Timsort在維基上的資料:https://en.wikipedia.org/wiki/Timsort