Leetcode合并有序数组：Python切片操作未达预期致输出错误

给定两个按非递减顺序排序的整数数组nums1和nums2，以及两个整数m和n，分别表示nums1和nums2中的元素数量。要求将nums1和nums2合并为一个按非递减顺序排序的数组，直接存储在nums1中（无需返回）。nums1的长度为m+n，前m个元素为有效元素，后n个0需忽略；nums2长度为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.
        """
        nums1 = nums1[:m]
        nums1+=nums2
        nums1.sort()

输入示例：

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3

实际输出：[1,2,3,0,0,0]
预期输出：[1,2,2,3,5,6]

错误原因 #

问题出在nums1 = nums1[:m]这一行：

• 这行代码创建了一个新的列表对象，包含原nums1的前m个元素，然后把这个新对象赋值给了局部变量nums1。
• 此时局部变量nums1已经和函数传入的原数组对象断开关联，后续的nums1+=nums2和nums1.sort()都是在这个新列表上操作，完全不会影响原数组。
• 题目要求原地修改nums1，也就是必须直接操作传入的原数组对象，不能重新赋值变量指向新对象。

修正方案 #

方案1：基于你的思路修改（原地覆盖） #

保留合并排序的思路，但要把结果写回原nums1：

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 先合并有效元素
        merged = nums1[:m] + nums2
        merged.sort()
        # 将合并后的结果逐个赋值回原nums1
        for i in range(m + n):
            nums1[i] = merged[i]

方案2：双指针最优解（时间O(m+n)，空间O(1)） #

从两个数组的末尾开始比较，把较大的元素放到nums1的末尾（利用nums1后面的空位置），不需要额外空间：

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 三个指针：i指向nums1有效元素末尾，j指向nums2末尾，k指向nums1整体末尾
        i, j, k = m - 1, n - 1, 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
        
        # 如果nums2还有剩余元素，全部放到nums1前面
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

内容的提问来源于stack exchange，提问作者mkj4332