頂尖訪(fǎng)談150

合併排序數(shù)組是一個(gè)經(jīng)典問(wèn)題，了解如何有效解決它對(duì)於編碼面試至關(guān)重要。在這篇文章中，我們將使用 JavaScript 來(lái)解決 LeetCode 的 88. 合併排序數(shù)組，這是頂級(jí)面試 150 個(gè)問(wèn)題挑戰(zhàn)的一部分。讓我們深入研究這個(gè)問(wèn)題、它的細(xì)微差別以及一個(gè)乾淨(jìng)、最佳的解決方案！

---

？問(wèn)題描述
給定兩個(gè)整數(shù)數(shù)組 nums1 和 nums2，按非降序排序。您的任務(wù)是將 nums2 合併到 nums1 中，使 nums1 保持排序狀態(tài)。

但是，有一個(gè)轉(zhuǎn)捩點(diǎn)：

nums1 有足夠的空間（設(shè)定為 0s）來(lái)容納 nums2 的元素。
最終的合併結(jié)果必須就地儲(chǔ)存在 nums1 中。

---

？範(fàn)例

範(fàn)例1

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

範(fàn)例2

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

範(fàn)例3

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

---

？主要見(jiàn)解

• 就地合併：需要填滿(mǎn)nums1而不使用額外的空間。這意味著直接修改數(shù)組。
• 從後到前的策略：由於nums1末尾有多餘的空間，最有效的方法是從後面填充。

---

？ JavaScript 解決方案：兩指標(biāo)方法

最佳解法利用雙指標(biāo)方法，從兩個(gè)陣列的末端開(kāi)始。這確保了最大的元素首先放置，避免不必要的元素移動(dòng)。

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. 從末尾開(kāi)始：
   比較 nums1 和 nums2 的最大元素（使用 p1
   和 p2 指標(biāo)）。將較大的元素放在
   的末尾 nums1（使用 p 指標(biāo)）。

2. 遞減指針：
   在處理元素時(shí)移動(dòng) p1、p2 和 p。

3. 處理剩餘元素：
   如果 nums2 中還有剩餘元素，則複製到 nums1 中。 （沒(méi)有
   需要從 nums1 複製元素，因?yàn)樗鼈円呀?jīng)就位。 ）

---

？複雜度分析

？試運(yùn)行
輸入：
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 上的完整問(wèn)題和測(cè)試案例。挑戰(zhàn)自己，在不看程式碼的情況下實(shí)現(xiàn)解決方案！

---

? 面試專(zhuān)業(yè)技巧

1. 澄清限制：詢(xún)問(wèn)您是否可以使用額外的空間，或者如果- 地點(diǎn)為必填項(xiàng)。
2. 針對(duì)邊緣情況進(jìn)行最佳化：考慮 nums2 為空的情況 或 nums1 沒(méi)有初始元素 (m = 0)。
3. 演練你的邏輯：解釋兩指標(biāo)方法 向面試官說(shuō)清楚。

---

---

有任何問(wèn)題或見(jiàn)解嗎？在下面的評(píng)論中分享吧！我們一起來(lái)學(xué)習(xí)吧。 ？

以上是LeetCode 挑戰(zhàn)：合併排序數(shù)組 - JavaScript 解決方案的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！