Leetcode 88 Merged Sorted Array

Leetcode 88 Merged Sorted Array"/>

Leetcode 88 Merged Sorted Array

Leetcode 88 Merged Sorted Array

题目描述

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.-
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

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

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路解析

与合并两个有序链表的思路相似，使用双指针法

class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""i = 0j = 0nums1_temp = nums1[0:m]nums1[:] = []while i < m and j < n:if nums1_temp[i] <= nums2[j]:nums1.append(nums1_temp[i])i += 1else:nums1.append(nums2[j])j += 1if i < m:nums1[i+j:] = nums1_temp[i:]if j < n:nums1[i+j:] = nums2[j:]

其时间复杂度为 O ( m + n ) O(m+n) O(m+n)，空间复杂度为 O ( m ) O(m) O(m)

注意第九行，由于题目中要求是就地修改nums1，所以得写成nums1[:] = []，而不能写成nums1 = []

• 一种对空间复杂度的改进

如果nums1的大小刚好可以容纳nums1和nums2的合并，则可以让双指针从后往前迭代，使算法的空间降为 O ( 1 ) O(1) O(1)

class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""i = m - 1j = n - 1p = m + n - 1while i >= 0 and j >= 0:if nums1[i] <= nums2[j]:nums1[p] = nums2[j]j -= 1else:nums1[p] = nums1[i]i -= 1p -= 1nums1[:j + 1] = nums2[:j + 1]