难度：简单

知识点：数组、双指针

地址：https://leetcode-cn.com/problems/merge-sorted-array

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

 

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:

nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: 

[1,2,2,3,5,6]

思路

• 既然是练习算法，我们就不用 sort() 这种套娃的方法了。
• 看到题目的第一想法是用双指针，由左向右比较，较小的依次插入。这样有个问题，插入时被替换的值，后续的排序会比较复杂
• 再看题目，既然 nums1 结尾留出了足够的空间在存放 nums2 的数据，那双指针可以从右向左开始遍历，依次将较大插入到 nums1 的尾部。
• 最后如果 nums2 遍历完毕，则完成，否则将 nums2 剩下的数据遍历存放到 nums1 开头即可。

from typing import *
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        执行用时： 48 ms , 在所有 Python3 提交中击败了 24.77% 的用户
        内存消耗： 13.4 MB , 在所有 Python3 提交中击败了 6.90% 的用户
        """
        i = -1
        while m > 0 and n > 0:
            if nums2[n-1] >= nums1[m-1]:
                nums1[i] = nums2[n-1]
                n -= 1
            else:
                nums1[i] = nums1[m-1]
                m -= 1
            i -= 1
        
        if n > 0:
            for j in range(n):
                nums1[j] = nums2[j]
            
        
        
        
s = Solution()
nums1 = [1,2,3,0,0,0]
s.merge(nums1, 3, [2,5,6], 3) 
assert nums1 == [1,2,2,3,5,6]