題目:

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

給定兩個list和m,n兩個整數
第一個list(l1)長度為m+n,前m項為要排序的值(sorted),後n項為0
第二個list(l2)長度為n,裡面都是要排序的值(sorted)
最後不用回傳任何東西,只要將l1變成含有l1,l2需排序元素且長度維持m+n的sorted list即可
ex:input:[1,2,3,0,0,0],m = 3,[2,5,6],n = 3 => output:[1,2,2,3,5,6]

這題我想了一陣子,還是想不到該如何讓兩個list結合,主要是那些0卡住了不少操作
直到我換個方向思考,才發現那些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.
        """       
        k=m+n-1
        
        while m>0 and n>0:
            if nums1[m-1]>=nums2[n-1]:
                nums1[k]=nums1[m-1]
                m=m-1
                k=k-1
            else:
                nums1[k]=nums2[n-1]
                n=n-1
                k=k-1
                
        while n>0:
            nums1[k]=nums2[n-1]
            n=n-1
            k=k-1
        return

由後面開始排序,這題會簡單很多
l1從第m項,l2從第n項,兩者由後往前比大小,較大的填入後該list指標往前
另立一個指標k=m+n-1紀錄要填入值的位置,隨著值的填入而往前
如此直到其中一個指標走完
如果是l2先走完,那代表l2的值已經全部填入l1內了,加上原本就是sorted list,因此到此l1就是我們要的形式了
如果是l1先走完,那表示l2還沒填入的值都比l1最小的值還小
因此假設當l2還剩x項時,就將這些值按序放入l1的前x項即可
最後執行時間40ms(faster than 89.05%)

那我們下題見