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)，直到num1或num2的结尾，
   也就是 i或j已指到end of array
   aka i指到m-1或j指到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

Result:

• Modify nums1 in-place version:
  
• Submissions:
  

Level:Easy