题目已刷,链接:LeetCode-题库-刷题(1-3)
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n,这样它就有足够的空间保存来自 nums2 的元素。
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.
"""
tail = m + n - 1
m-=1
n-=1
while n >= 0:
if m>=0 and nums1[m] > nums2[n]:
nums1[tail],nums1[m]= nums1[m],nums1[tail]
m -= 1
else:
nums1[tail] = nums2[n]
n -= 1
tail -= 1
思路:逆向双指针,逆序寻找两个数组最大的,nums1和nums2数谁大,则填入nums1后面的空缺。如果是nums1大,则进行tail指针与m指针数进行互换(防止出现复制值现象),如果nums2大则直接赋值给tail 位置。依次类推进行,m>=0
表示nums[1]
有序序列未排完,若排完则就让nums2继续排列。
func merge(nums1 []int, m int, nums2 []int, n int) {
tail:=m+n-1
for m,n=m-1,n-1;n>=0;tail--{
if m>=0 && nums1[m]>nums2[n]{
nums1[m],nums1[tail]=nums1[tail],nums1[m]
m--
}else{
nums1[tail]=nums2[n]
n--
}
}
}
思路:可见python。