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]
更多推荐
Leetcode 88 Merged Sorted Array
发布评论