How does the two-pointer approach solve the 'Merge Sorted Array' problem?

The two-pointer approach starts at the end of both arrays, comparing and placing the largest elements in the right positions within nums1, ensuring an in-place merge.

What should be done when nums2 is empty?

If nums2 is empty, no elements need to be merged, and nums1 remains unchanged, as its first m elements are already sorted.

Why is the space complexity O(1) in this problem?

Since we are merging the arrays in-place within nums1 without using extra arrays, the space complexity remains O(1).

How do you handle the zeros in nums1 when merging?

The zeros act as placeholders. By merging from the back of nums1, we can avoid overwriting valid elements while filling nums1 with merged values.

What are common edge cases for the 'Merge Sorted Array' problem?

Edge cases include when nums2 is empty, nums1 is initially empty, or when the arrays are already sorted. These scenarios need special handling for efficiency.

#88

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

合并两个有序数组

给你两个按非递减顺序排列的整数数组 nums1 和 nums2 ，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 num…

数组双指针排序

题目描述

给你两个按 非递减顺序 排列的整数数组 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
-10⁹ <= nums1[i], nums2[j] <= 10⁹

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

lightbulb

解题思路

方法一：双指针

我们注意到数组的有序性，可以使用双指针的方法，从后向前遍历两个数组，每次取两个数组中较大的一个放进合并后的数组的最后面。

具体地，我们用两个指针 $i$ 和 $j$ 分别指向两个数组的末尾，用一个指针 $k$ 指向合并后的数组的末尾。每次比较两个数组的末尾元素，将较大的元素放在合并后的数组的末尾，然后将指针向前移动一位，重复这个过程，直到两个数组的指针都指向了数组的开头。

时间复杂度 $O(m + n)$ ，其中 $m$ 和 $n$ 分别是两个数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how to efficiently merge arrays in-place?
question_mark
Can you explain why the two-pointer technique is optimal for this problem?
question_mark
Will you consider edge cases like when one of the arrays is empty?

warning

常见陷阱

外企场景

error
Overwriting elements in nums1 before reaching the end, which can lead to data loss.
error
Forgetting to handle the case when nums2 is empty, which should result in no changes to nums1.
error
Assuming that elements of nums1 after m are zero and should be directly ignored, without considering the potential for overflow or incorrect indexing.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Merge k sorted arrays using a similar two-pointer technique.
arrow_right_alt
Merge two sorted linked lists in place.
arrow_right_alt
Merge two arrays without extra space, considering the possibility of unequal sizes.

help

常见问题

外企场景

继续练习

#75 颜色分类 #18 四数之和 #16 最接近的三数之和