LC88. 合并两个有序数组

# 登录 AlgoMooc 官网获取更多算法图解
# https:#www.algomooc.com/555.html
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 合并两个有序数组( LeetCode 88 ):https:#leetcode-cn.com/problems/merge-sorted-array/
class Solution :
   def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 索引从有序数组 nums1 有效元素的末端开始
        # 数组的下标索引从零开始计数
        # 索引   0    1     2
        # 数组 [ 1 ,  2  ,  3 ]
        i = m - 1

        # 索引从有序数组 nums2 的末端开始
        j = n - 1

        # 从有序数组 nums1 最末端的位置开始保存元素
        cur = m + n - 1

        # 通过循环把 num2 的元素都移动到 num1 中
        while j >= 0  :

            # 比较 num1 和 num2 中当前的元素大小

            # 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
            # 为了防止越界 i 必须是大于等于 0 
            if  i >=0 and nums1[i] > nums2[j]:

             # 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
             # 此时 cur 的元素已经确定下来
             nums1[cur] = nums1[i]
            
             # 接下来去确定 cur 前面一个元素应该放什么数字
             cur-=1
             # 此时，索引 i 需要向前移动
             i-=1
             # 否则，如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
            else:
             
             # 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
             nums1[cur] = nums2[j]
             # 接下来去确定 cur 前面一个元素应该放什么数字
             cur-=1
             # 此时，索引 j 需要向前移动
             j-=1


# 题目：LC88. 合并两个有序数组
# 难度：简单
# 作者：许老师-闭着眼睛学数理化
# 算法：双指针
# 代码看不懂的地方，请直接在群上提问


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # i是nums1的下标（不包含0的部分）
        # j是nums2的下标
        i = m - 1
        j = n - 1
        # cur是nums1的下标（包含最后的0的部分）
        cur = m + n - 1
        # 我们需要把所有nums2中的值放到nums1中，故要求j >= 0
        # 当j == -1时，说明nums2中所有的元素均已经放到nums1中了
        # 此时可以退出循环
        while j >= 0:
            # 如果i < 0，说明nums1中的值已经用完
            # 把nums2[j]放到nums1[cur]，cur和j均递减
            if i < 0:
                nums1[cur] = nums2[j]
                cur -= 1
                j -= 1
            # i >= 0的情况，nums1中的值还没有用完
            else:
                # nums1[i]大于等于nums2[j]，nums1[i]要放到nums1[cur]
                # 然后cur和i均递减
                if nums1[i] >= nums2[j]:
                    nums1[cur] = nums1[i]
                    cur -= 1
                    i -= 1
                # nums1[i]小于nums2[j]，nums2[j]要放到nums1[cur]
                # 然后cur和j均递减
                # 以下内容可以合并到i < 0的情况，即变成吴师兄的代码
                else:
                    nums1[cur] = nums2[j]
                    cur -= 1
                    j -= 1

        

四、复杂度分析
时间复杂度：O(m+n)。指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
空间复杂度：O(m+n)。