LeetCode: 88 Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2, respectively.
You need to merge nums2 into nums1 as one sorted array. The final sorted array should not be returned by the function, but instead, be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored.

Example

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6].

问题

你有两个按 非递减顺序 排列的整数数组 nums1 和 nums2，以及两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数量。
你需要将 nums2 合并到 nums1 中，作为一个排序后的数组。最终的排序数组不需要返回，而是存储在 nums1 中。为了容纳这个合并的数组，nums1 的长度是 m + n，前 m 个元素表示要合并的元素，最后的 n 个元素设置为 0，应该被忽略。

例子

输入: 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]。

Solution

Approach: Two Pointers from the End / 双指针从末尾开始

We use two pointers, one for nums1 and one for nums2, starting from the end of the non-zero elements. We compare the elements and place the larger element at the end of nums1. This approach is efficient because we take advantage of the extra space at the end of nums1 to insert the largest elements first.

Approach Explanation / 方法解释

Start two pointers: p1 at m-1 for nums1 and p2 at n-1 for nums2.
Iterate from the end of the array, placing the largest value at the current position in nums1 and moving the corresponding pointer (p1 or p2) backwards.
If there are remaining elements in nums2, copy them over to nums1.

Recurrence / 递推关系

nums1[last] = max(nums1[p1], nums2[p2])

This ensures that we are filling the nums1 array from the largest values down to the smallest.

Implementation / 实现

Python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1, p2, last = m - 1, n - 1, m + n - 1

        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[last] = nums1[p1]
                p1 -= 1
            else:
                nums1[last] = nums2[p2]
                p2 -= 1
            last -= 1

        while p2 >= 0:
            nums1[last] = nums2[p2]
            p2 -= 1
            last -= 1

Explanation / 解释

Initialize Pointers / 初始化指针
```
p1, p2, last = m - 1, n - 1, m + n - 1
```
- English: We set the pointers p1 and p2 to the last elements of nums1 and nums2, respectively, and last to the last index of nums1.
- Chinese: 我们将指针 p1 和 p2 设置为 nums1 和 nums2 的最后一个元素，并将 last 设置为 nums1 的最后一个索引。
Merge Arrays / 合并数组
```
while p1 >= 0 and p2 >= 0:
   if nums1[p1] > nums2[p2]:
       nums1[last] = nums1[p1]
       p1 -= 1
   else:
       nums1[last] = nums2[p2]
       p2 -= 1
   last -= 1
```
- English: Compare nums1[p1] and nums2[p2]. Place the larger value at nums1[last] and move the corresponding pointer back.
- Chinese: 比较 nums1[p1] 和 nums2[p2]。将较大的值放在 nums1[last]，并将相应的指针向后移动。
Copy Remaining Elements / 复制剩余元素
```
while p2 >= 0:
   nums1[last] = nums2[p2]
   p2 -= 1
   last -= 1
```
- English: If there are remaining elements in nums2, copy them to nums1.
- Chinese: 如果 nums2 中有剩余的元素，将它们复制到 nums1 中。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(m + n), because we process each element in nums1 and nums2 exactly once.
Space Complexity / 空间复杂度: O(1), since we only use a few extra variables for pointers and no additional arrays.

Key Concept / 关键概念

Two Pointers / 双指针: Using two pointers from the end allows us to efficiently merge the arrays in-place, utilizing the empty space at the end of nums1.
双指针: 使用从末尾开始的双指针让我们可以高效地就地合并数组，利用 nums1 末端的空余空间。

Summary / 总结

English: Merging two sorted arrays in-place can be efficiently done using two pointers, starting from the end of the arrays. This avoids the need for extra space and ensures an O(m + n) time complexity.
Chinese: 合并两个排序数组可以通过双指针从末尾开始高效地就地完成。这避免了额外空间的需求，并保证了 O(m + n) 的时间复杂度。

Tips / 提示

English: Practice two-pointer techniques when merging arrays or subarrays, as it is a common technique in many array manipulation problems.
Chinese: 练习双指针技巧，特别是在合并数组或子数组时，因为这是许多数组操作问题中常见的技巧。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: To further improve your understanding of two-pointer techniques, practice problems that involve merging arrays, subarrays, and intervals.
Chinese: 为了进一步提高对双指针技术的理解，练习涉及合并数组、子数组和区间的问题。

Merge Sorted Array – Leetcode 88 – Python by NeetCode

Post Views: 14

CODEBITWAVE