本文共 2276 字，大约阅读时间需要 7 分钟。

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中*，*使得 num1 成为一个有序数组。

说明:

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
• 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6],       n = 3输出: [1,2,2,3,5,6]

解题思路

这个问题没什么好说的，就是考察归并排序中的merge操作。

class Solution:    def merge(self, nums1, m, nums2, n):        """        :type nums1: List[int]        :type m: int        :type nums2: List[int]        :type n: int        :rtype: void Do not return anything, modify nums1 in-place instead.        """        nums1[m:] = nums2[:n]        all_list = nums1.copy()        all_len = m + n        i = 0        j = m        for k in range(all_len):            if i > m - 1:                nums1[k] = all_list[j]                j += 1            elif j > all_len - 1:                nums1[k] = all_list[i]                i += 1            elif all_list[i] < all_list[j]:                nums1[k] = all_list[i]                i += 1            else:                nums1[k] = all_list[j]                j += 1

注意这里有一个陷阱，我们必须使用all_list = nums1.copy()，使用all_list = nums1是不行的。这是因为后者表达的意思是all_list和nums1指向的是同一片内存空间，如果nums1变化的话，all_list也会随之改变。

但是我们一直忽略了题目中的条件两个有序整数数组，所以我们有一个更好的解法。我们可以直接比较nums1和nums2元素的大小，然后根据大小加入到nums1的末尾，最后还要考虑nums2的元素是否还有剩余即可。

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

python的sort是，也就是归并排序的优化版本，所以最简洁的写法就是：

class Solution:    def merge(self, nums1, m, nums2, n):        """        :type nums1: List[int]        :type m: int        :type nums2: List[int]        :type n: int        :rtype: void Do not return anything, modify nums1 in-place instead.        """            nums1[m:] = nums2[:n]        nums1.sort()

该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/80500807 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！