【力扣日记】088合并两个顺序配列|面接问题10.01

タイトルの説明
2つの秩序整数配列nums 1およびnums 2が与えられ、nums 2がnums 1に結合され、num 1が秩序配列になる.
説明:nums 1とnums 2を初期化する要素の数は、それぞれmとnです.nums 1にはnums 2の要素を保存するのに十分な空間(空間サイズがm+n以上)があると仮定できます.
入力:nums 1=[1,2,3,0,0],m=3 nums 2=[2,5,6],n=3
出力:[1,2,2,3,5,6]
アルゴリズムの考え方
1、内蔵関数

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[m:]=nums2
        nums1.sort()

2、ダブルポインタ
2つの配列の1つの要素のみを比較します.

        i,j,ls=0,0,[]
        while i<m and j<n:
            if nums1[i]>nums2[j]:
                ls.append(nums2[j])
                j+=1
            elif nums1[i]<=nums2[j]:
                ls.append(nums1[i])
                i+=1
        if i==m:nums1[:]=ls+nums2[j:]
        else:nums1[:]=ls+nums1[i:m]

実行時間:28 ms、すべてのPython 3コミットで99.22%のユーザーメモリ消費量:12.9 MBを破り、すべてのPython 3コミットで46.72%のユーザーを破った
3、popを使う
考えは二重ポインタに等しいが、もっと簡潔だ.

        ls,A[:]=[],A[:m]
        while A and B:
            if A[-1]>B[-1]:
                ls.append(A.pop())
            else:
                ls.append(B.pop())
        if A:A[:]=A+ls[::-1] 
        else:A[:]=B+ls[::-1]

実行時間:32 ms、すべてのPython 3コミットで95.35%のユーザーを破った
4、その場で修正

        A[:],i,j=A[:m],0,0
        while i<len(A) and j<n:
            if B[j]<=A[i]:
                A.insert(i,B[j])
                j+=1
            else:i+=1
        if j<n:A.extend(B[j:n])

実行時間:36 ms、すべてのPython 3コミットで89.15%のユーザーを破った