合并两个有序数组

大家好，欢迎来到IT知识分享网。

88. 合并两个有序数组

提示

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。 

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。 

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。 

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

当你需要在原地修改 nums1 数组而不返回任何东西时，你可以采用类似的方法来解决这个问题，即从后向前合并。这种方法的关键点在于，由于 nums1 的后部分是空的，可以用来存放合并后的数组，从而避免额外的空间开销。

这里是具体的 Python 解法，它遵循了先前描述的双指针法，并在原地修改 nums1：

pythonCopy code

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: p1, p2 = m - 1, 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[:p2 + 1] = nums2[:p2 + 1]

这个方法直接修改了 nums1，并且没有返回值，符合题目要求的“原地修改”。由于这个方法从后向前填充 nums1，因此可以确保在合并的过程中不会覆盖 nums1 中尚未处理的元素。

• 这行定义了一个名为 Solution 的类。在 LeetCode 中，解题函数通常被放置在一个类中。

pythonCopy code

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:

• 这行定义了 merge 方法，它是 Solution 类的一部分。该方法接受四个参数：nums1 和 nums2（两个整数数组），m 和 n（分别是 nums1 和 nums2 中的元素数量）。-> None 表明这个方法没有返回值，即它会原地修改 nums1。

pythonCopy code

p1, p2 = m - 1, n - 1

• 这行初始化两个指针 p1 和 p2。p1 指向 nums1 中最后一个有效元素，p2 指向 nums2 中最后一个元素。由于数组索引是从 0 开始的，所以使用 m - 1 和 n - 1。

pythonCopy code

p = m + n - 1

• 这行初始化指针 p，它指向 nums1 数组合并后应放置最后一个元素的位置。

pythonCopy code

while p1 >= 0 and p2 >= 0:

• 这个循环继续执行，直到 p1 或 p2 其中一个到达数组的开始位置。这意味着它会比较 nums1 和 nums2 中的元素，并根据大小将它们放置在正确的位置。

pythonCopy code

if nums1[p1] > nums2[p2]:

• 如果 nums1[p1] 的元素大于 nums2[p2] 的元素，这意味着 nums1[p1] 应该放在当前合并数组的末尾。

pythonCopy code

nums1[p] = nums1[p1] p1 -= 1

• 把 nums1[p1] 放在 nums1[p] 的位置上（即合并数组的当前末尾），然后将 p1 指针向左移动，准备比较下一个元素。

pythonCopy code

else: nums1[p] = nums2[p2] p2 -= 1

• 如果 nums2[p2] 的元素大于或等于 nums1[p1]，将 nums2[p2] 放在 nums1[p] 的位置上，然后将 p2 指针向左移动。

pythonCopy code

p -= 1

• 不论是 nums1[p1] 还是 nums2[p2] 被放在了 nums1[p] 的位置，都将 p 向左移动，以便下一次比较和放置元素。

pythonCopy code

nums1[:p2 + 1] = nums2[:p2 + 1]

• 循环结束后，如果 nums2 中还有剩余元素（这意味着 nums2 的所有元素都小于 nums1 的初始元素），这些元素直接复制到 nums1 的开始位置。这是必要的，因为上面的循环只在两个数组都有剩余元素时才运行。

整个函数的目的是在不使用额外空间的情况下，将两个已排序的数组合并为一个。通过从后向前合并元素，可以确保 nums1 的初始元素不会在合并过程中被覆盖。

解法二 简单代码版本

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: while m > 0 and n > 0: if nums1[m - 1] > nums2[n - 1]: nums1[m + n - 1] = nums1[m - 1] m -= 1 else: nums1[m + n - 1] = nums2[n - 1] n -= 1 nums1[:n] = nums2[:n] 

• 这行定义了 merge 方法，它是 Solution 类的一部分。该方法接受四个参数：nums1 和 nums2（两个整数列表），m 和 n（分别表示 nums1 和 nums2 中有效元素的数量）。-> None 指出这个方法没有返回值，即它会原地修改 nums1。

while m > 0 and n > 0:

• 这行定义了一个循环，持续进行直到 m 或 n 中的一个变为 0。这里 m 和 n 直接作为指向 nums1 和 nums2 中当前待合并元素的指针使用。

if nums1[m - 1] > nums2[n - 1]:

• 这里比较 nums1 和 nums2 当前待合并元素的值。如果 nums1 中的元素更大，它应该被放置在合并后数组的当前位置上。

nums1[m + n - 1] = nums1[m - 1] m -= 1

• 如果 nums1[m - 1] 更大，将其值复制到 nums1[m + n - 1]（即合并数组的当前末尾），然后将 m 减 1，以指向 nums1 中的下一个待合并元素。

else: nums1[m + n - 1] = nums2[n - 1] n -= 1

• 如果 nums2[n - 1] 的值更大或两者相等，则将 nums2[n - 1] 的值复制到 nums1[m + n - 1]，然后将 n 减 1，以指向 nums2 中的下一个待合并元素。

nums1[:n] = nums2[:n]

• 在循环结束后，如果 nums2 中还有未合并的元素（即 n > 0），这行代码会将这些剩余元素复制到 nums1 的开头。如果 n 为 0，这一步不会执行任何操作。

这种方法的核心在于它直接使用 m 和 n 作为指针来跟踪 nums1 和 nums2 中当前待合并的元素，从而减少了代码行数并保持了算法的效率。

# class Solution: # def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: # while m > 0 and n > 0: # if nums1[m - 1] > nums2[n - 1]: #比较 nums1 和 nums2 当前待合并元素的值。 #如果 nums1 中的元素更大，它应该被放置在合并后数组的当前位置上。 # nums1[m + n - 1] = nums1[m - 1] # m -= 1 #如果 nums1[m - 1] 更大，将其值复制到 nums1[m + n - 1]（即合并数组的当前末尾），然后将 m 减 1，以指向 nums1 中的下一个待合并元素。 # else: # nums1[m + n - 1] = nums2[n - 1] # n -= 1 # 如果 nums2[n - 1] 的值更大或两者相等，则将 nums2[n - 1] 的值复制到 nums1[m + n - 1]，然后将 n 减 1，以指向 nums2 中的下一个待合并元素。 # nums1[:n] = nums2[:n] #在循环结束后，如果 nums2 中还有未合并的元素（即 n > 0），这行代码会将这些剩余元素复制到 nums1 的开头。如果 n 为 0，这一步不会执行任何操作。