iT邦幫忙

2021 iThome 鐵人賽

DAY 5
1
自我挑戰組

FRIENDS系列 第 5

Day 5: LeetCode 88. Merge Sorted Array

Tag:隨意刷-[50-100] LeetCode Problem

Source:

88. Merge Sorted Array

1.題意:

  • Merge(合併)兩個已排列(由小至大)陣列(nums1、nums2)
  • 建議採用In place方式(見程式碼comment)將num2併入num1
  • num1 長度為m,num2 長度為n,合併元素為num1的前m個與num2的前n

Note:

  • In-place algorithm

    In computer science, an in-place algorithm is an algorithm
    which transforms input using no auxiliary data structure.
    aka 對num1、num2直接操作,不使用額外變數(記憶體)來輔助來取得結果

2.思路:

  1. 非in place版-直觀解
    使用額外變數tmpList
    m個到tmpList
    再放n個到tmpList
    清空nums1.clear()
    Copy tmpList to nums1
    進行sort ➔ .sort()

  2. 非in place版-merge sort の merge
    兩個指針 i, j 初始分別指向num1與num2的第0個位置,比較值的大小(由小的開始放),
    放入較小的元素進輔助變數(ans),直到num1num2的結尾,
    也就是 ij已指到end of array
    aka i指到m-1j指到n-1
    接著放另一個還未到結尾的array進ans
    清空nums1.clear()
    迴圈法將ans中的每個元素加入nums1

  3. in place版-參考Discuss神人解
    兩陣列取大放(m+n-1)位置,被取的往前(往值小)移動,
    同一時間最終合併陣列-num1的(m+n-1)值會往前移,直到num2的元素用完(n為0)。

3.程式碼:

[非in place版-直觀解]

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        tmpList = []
        for i in range(m):
            tmpList.append(nums1[i])
        for j in range(n):
            tmpList.append(nums2[j])
            
        nums1.clear()
        for k in range(m+n):
            nums1.append(tmpList[k])
        nums1.sort()    
        print(nums1)    

[非in place版-merge sort の merge]

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = 0
        j = 0
        ans = []
        while i<m and j<n:
            if nums1[i]<nums2[j]:
                ans.append(nums1[i])
                i+=1
            else:
                ans.append(nums2[j])
                j+=1
        
        print("i-j",i,j)
        
        while i<=(m-1):
            ans.append(nums1[i])
            i+=1
        while j<=(n-1):
            ans.append(nums2[j])
            j+=1
        nums1.clear()
        for k in ans:
            nums1.append(k)    

More Info. Python Program for Iterative Merge Sort

[in place版-參考Discuss神人解]

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.
        """
        while n:
            if m and nums1[m-1]>nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m-=1
            else:
                nums1[m+n-1] = nums2[n-1]
                n-=1

More Info. Beautiful Python Solution/Comments/@clarencechee
https://ithelp.ithome.com.tw/upload/images/20210920/20111516DcjsDsVunE.png

Result:

  • Modify nums1 in-place version:
    https://ithelp.ithome.com.tw/upload/images/20210920/20111516A2sUbJvDgN.png
  • Submissions:
    https://ithelp.ithome.com.tw/upload/images/20210920/20111516iI1Nn2LZcR.png

Level:Easy


上一篇
Day 4: LeetCode 995. Minimum Number of K Consecutive Bit Flips(v2)
下一篇
Day 6: LeetCode 54. Spiral Matrix
系列文
FRIENDS30

尚未有邦友留言

立即登入留言