给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
分析:
方法一: 首先将两个数组中元素合并在num1中,然后对新得到的数组中元素重新排序。
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: nums1[:] = sorted(nums1[:m] + nums2)方法二: 通过借助第三个数组,将两个数组中的元素按顺序添加到nums1中。关键点:①利用两个指针分别指向两个元组元素进行比较;②对于剩余的较大元素的处理。
class Solution(object): def merge(self, nums1, m, nums2, n): # 将数组 nums1中的元素赋值在一个新的元组后,令 nums1为空列表. nums1_copy = nums1[:m] nums1[:] = [] # 分别使用p1和p2两个指针指向数组 nums1_copy和 nums2. p1 = 0 p2 = 0 # 按照先后顺序对两个数组中元素的大小作比较,并选择最小的元素添加到列表 nums1中. while p1 < m and p2 < n: if nums1_copy[p1] < nums2[p2]: nums1.append(nums1_copy[p1]) p1 += 1 else: nums1.append(nums2[p2]) p2 += 1 # 对于两个元组中剩余的元素 if p1 < m: nums1[p1 + p2:] = nums1_copy[p1:] if p2 < n: nums1[p1 + p2:] = nums2[p2:]方法三: 为了节省方法二中的空间复杂度,即:不使用第三个列表“nums1_copy”,通过逆序的方式,将nums2中元素添加到nums1中。
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: # 指定 nums1 和 nums2 的两个指针,分别指两数组的最大值 p1 = m - 1 p2 = n - 1 # 指定 len(nums1)=m+n-1的 数组指针 p = m + n - 1 # 判断:将两数组中的最大值放置在最终数组中的最后位置。 while p1 >= 0 and p2 >= 0: if nums1[p1] < nums2[p2]: nums1[p] = nums2[p2] p2 -= 1 else: nums1[p] = nums1[p1] p1 -= 1 p -= 1 # 如果nums2中还有剩余元素,则将其添加到最前面的位置。 nums1[:p2 + 1] = nums2[:p2 + 1]结论:对于两个数组中元素的排序方式分为:全排序,从小到大排序和从大到小排序。