LeetCode热题100-88. 合并两个有序数组

这个题不在hot-100给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数m和n分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中使合并后的数组同样按非递减顺序排列。注意最终合并后数组不应由函数返回而是存储在数组nums1中。为了应对这种情况nums1的初始长度为m n其中前m个元素表示应合并的元素后n个元素为0应忽略。nums2的长度为n。首先想到的就是合并后排序就OK时间复杂度为O(mn)log(mn).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. l m for i in range(len(nums2)): nums1[l] nums2[i] l 1 nums1.sort()第二种依赖数组有序可以使用三针指的方法。时间复杂度O(m n)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 - 1 j n - 1 k m n -1 while i 0 and j 0: if nums1[i] nums2[j]: nums1[k] nums1[i] i - 1 else: nums1[k] nums2[j] j - 1 k - 1 while j 0: nums1[k] nums2[j] j - 1 k - 1