pythontip 100days-day21

Code › python
, ,

题目

给你两个升序整数数组 nums1 和 nums2，请你将 nums2 按升序合并到到新的数组并返回。

例子

merge([1,2,3],[2,5,6]) -> [1,2,2,3,5,6]
merge([1,2,3,7],[4,5,6]) -> [1,2,3,4,5,6,7]

假设

  1. 输入的数组均不为空
  2. 输入的数组均为升序

tips

  1. 利用数组有序的性质
  2. 避免全局排序

答案

解法1

def merge(nums1,nums2):
    i , j = 0 , 0
    merged = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    if i < len(nums1):
        for num in nums1[i : ]:
            merged.append(num) 
    if j < len(nums2):
        for num in nums2[j : ]:
            merged.append(num)
    return merged

性能：

  1. 时间复杂度O(n)
  2. 空间复杂度O(n)

关键点：

  1. 利用数组有序的性质
  2. 避免全局排序