[LeetCode]88-合并两个有序数组

88. 合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

示例:

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

输出: [1,2,2,3,5,6]

解法1: 借助其他的列表空间来完成

class Solution:
    def merge(self, nums1, m, nums2, n):
       list1 = nums1[:m]
        list2 = nums2[:n]
        for i in list2:
            list1.append(i)
        list1.sort()
        for i in range(len(list1)):
            nums1[i] = list1[i]

解法2: 直接在nums1上操作, 从大的数开始排序

class Solution:
    def merge(self, nums1, m, nums2, n):
        while m>0 and n >0:
            if nums1[m-1] >= nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m = m -1
            else :
                nums1[m+n-1] = nums2[n-1]
                n = n-1
        # 从大到小排, 排一个大的数就减1, 最后剩下的就是最小的
        if n > 0 :
            nums1[:n] = nums2[:n]

解法3: 依然是从大的数开始排, 更直观的版本

class Solution:
    def merge(self, nums1, m, nums2, n):
        p1 = m-1    # 数组1的最后一位
        p2 = n-1    # 数组2的最后一位
        for i in range(m+n):    # 最后合并的数组一共有m+n位
            if p2 < 0:  # p2小于零, 即数组2是空的, 直接返回
                return
            if p1 < 0:  # p1小于零, 即数组1是空的, 直接把数组2顺序赋值给数组1
                for j in range(p2+1):
                    nums1[j] = nums2[j]
                return
            if nums1[p1] > nums2[p2]:   # 数组1的最后一位大于数组2的最后一位
                nums1[m+n-1-i] = nums1[p1]  # 将最大的数归位
                p1 -= 1
            else:   # 数组1的最后一位小于数组2的最后一位
                nums1[m+n-1-i] = nums2[p2]  # 将最大的数归位
                p2 -= 1

思考: 怎么从小的数开始排.