LeetCode 挑战：合并排序数组 - JavaScript 解决方案

顶级访谈150

合并排序数组是一个经典问题，了解如何有效解决它对于编码面试至关重要。在这篇文章中，我们将使用 JavaScript 来解决 LeetCode 的 88. 合并排序数组，这是顶级面试 150 个问题挑战的一部分。让我们深入研究这个问题、它的细微差别以及一个干净、最佳的解决方案！

---

？问题描述
给定两个整数数组 nums1 和 nums2，按非降序排序。您的任务是将 nums2 合并到 nums1 中，使 nums1 保持排序状态。

但是，有一个转折点：

nums1 有足够的空间（设置为 0s）来容纳 nums2 的元素。
最终的合并结果必须就地存储在 nums1 中。

---

？示例

示例1

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

示例2

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

示例3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

---

？主要见解

• 就地合并：需要填充nums1而不使用额外的空间。这意味着直接修改数组。
• 从后到前的策略：由于nums1末尾有多余的空间，最有效的方法是从后面填充。

---

？ JavaScript 解决方案：两指针方法

最佳解决方案利用双指针方法，从两个数组的末尾开始。这确保了最大的元素首先放置，避免不必要的元素移动。

var merge = function(nums1, m, nums2, n) {
    // Initialize pointers for nums1, nums2, and the last index of nums1
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    // Compare elements from the end and place the largest at the back
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    // Copy remaining elements from nums2 (if any)
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
};

---

？工作原理

1. 从末尾开始：
   比较 nums1 和 nums2 的最大元素（使用 p1
   和 p2 指针）。将较大的元素放在
   的末尾 nums1（使用 p 指针）。

2. 递减指针：
   在处理元素时移动 p1、p2 和 p。

3. 处理剩余元素：
   如果 nums2 中还有剩余元素，则将其复制到 nums1 中。 （没有
   需要从 nums1 复制元素，因为它们已经就位。）

---

？复杂度分析

？试运行
输入：
nums1 = [1,2,3,0,0,0]，m = 3，nums2 = [2,5,6]，n = 3

步骤 p1 p2 p nums1
初始化 2 2 5 [1,2,3,0,0,0]
1 2 2 5 [1,2,3,0,0,6]
2 2 1 4 [1,2,3,0,5,6]
3 2 0 3 [1,2,3,3,5,6]
4 1 0 2 [1,2,2,3,5,6]
5 0 0 1 [1,2,2,3,5,6]
最终输出：[1,2,2,3,5,6]

---

？自己尝试一下吧！

查看 LeetCode 上的完整问题和测试用例。挑战自己，在不看代码的情况下实现解决方案！

---

✨ 面试专业技巧

1. 澄清限制：询问您是否可以使用额外的空间，或者如果- 地点为必填项。
2. 针对边缘情况进行优化：考虑 nums2 为空的情况 或者 nums1 没有初始元素 (m = 0)。
3. 演练你的逻辑：解释两指针方法 向面试官说清楚。

---

---

有任何问题或见解吗？在下面的评论中分享吧！我们一起来学习吧。 ？

以上是LeetCode 挑战：合并排序数组 - JavaScript 解决方案的详细内容。更多信息请关注PHP中文网其他相关文章！