leetcode with python:88. Merge Sorted Array

题目:

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%)

那我们下题见