本地运行正常的LeetCode合并数组代码为何报索引越界错误？

题目要求 #

给定两个按非递减顺序排列的整数数组nums1和nums2，以及两个整数m和n，分别表示nums1和nums2中的元素数量。将nums1和nums2合并为一个按非递减顺序排列的数组，最终有序数组需存储在nums1内部（nums1长度为m+n，前m个元素为有效元素，后n个为0需忽略）。

提交代码 #

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.
        """

        if len(nums1) == 0:
            for i in range(len(nums2)):
                nums1.append(nums2[i])
                
        i, j = 0, 0

        templist = []

        while i < m and j < n:
            if nums1[i] < nums2[j]:
                templist.append(nums1[i])
                i += 1
            else:
                templist.append(nums2[j])
                j += 1

        for k in range(len(nums1)):
            nums1[k] = templist[k]

        while i < m:
            nums1.append(nums1[i])
            i += 1
        while j < n:
            nums1.append(nums2[j])
            j += 1

报错信息 #

IndexError: list index out of range
    nums1[k] = templist[k]
Line 24 in merge (Solution.py)
    ret = Solution().merge(param_1, param_2, param_3, param_4)
Line 66 in _driver (Solution.py)
    _driver()
Line 78 in <module> (Solution.py)

用户疑问 #

上述代码在本地电脑运行正常，但在LeetCode平台执行时触发索引越界错误，无法理解原因，请求分析与解决。

问题分析 #

索引越界的直接原因 #

代码里的templist仅在i<m且j<n的循环中添加元素，循环结束后，要么nums1的剩余有效元素未加入，要么nums2的剩余元素未加入，此时templist的长度必然小于m+n（即len(nums1)）。但后续用for k in range(len(nums1))循环给nums1赋值时，当k超过templist的长度，就会触发索引越界。

本地测试正常大概率是你刚好选择了templist长度等于m+n的测试用例（比如nums1和nums2的元素完全交替，刚好把所有元素都加入templist），但LeetCode的测试用例会覆盖更多场景，比如nums1的前m个元素都比nums2小，此时templist只有m个元素，循环到k=m时就会报错。

其他逻辑问题 #

1. 后续的nums1.append(...)操作错误：题目要求nums1保持m+n的长度，append会让数组变长，不符合原地修改的要求，且append原nums1的元素毫无意义。
2. 开头的if len(nums1) ==0判断多余：题目明确nums1初始长度为m+n，不可能为0，除非m和n都是0，此时无需处理。

解决方案 #

这里提供两种正确的实现方式：

方式一：从后往前合并（最优，无需额外空间） #

利用nums1后面的n个空位，从两个数组的末尾开始比较，将大的元素放到nums1的末尾，避免覆盖未处理的元素。

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有效元素末尾、nums2末尾、nums1整体末尾
        p1 = m - 1
        p2 = n - 1
        p = m + n - 1
        
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            p -= 1
        
        # 如果nums2还有剩余元素未处理，直接复制到nums1的前面
        nums1[:p2 + 1] = nums2[:p2 + 1]

方式二：用额外空间后覆盖nums1（逻辑简单） #

如果一定要用临时数组，需先将所有元素加入临时数组，再整体覆盖nums1：

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, j = 0, 0
        templist = []
        
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                templist.append(nums1[i])
                i += 1
            else:
                templist.append(nums2[j])
                j += 1
        
        # 添加nums1剩余的有效元素
        templist.extend(nums1[i:m])
        # 添加nums2剩余的元素
        templist.extend(nums2[j:n])
        
        # 整体覆盖nums1，确保原地修改
        nums1[:] = templist

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