LeetCode チャレンジ: ソートされた配列のマージ - JavaScript ソリューション

トップインタビュー 150

ソートされた配列のマージは古典的な問題であり、それを効率的に解決する方法を理解することは、インタビューのコーディングには不可欠です。この投稿では、JavaScript を使用して、LeetCode の「トップ インタビュー 150 の質問」チャレンジの一部である 88. ソートされた配列をマージする問題に取り組みます。問題とそのニュアンス、そしてクリーンで最適な解決策について詳しく見ていきましょう!

?問題の説明
非降順でソートされた 2 つの整数配列 nums1 と nums2 が与えられます。あなたのタスクは、nums1 がソートされたままになるように、nums2 を nums1 にマージすることです。

ただし、工夫があります:

nums1 には、nums2 の要素を収容するのに十分なスペース (0 に設定) があります。
最終的なマージ結果は、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 ソリューション: 2 点アプローチ

最適な解決策は、両方の配列の末尾から開始する 2 ポインター アプローチ を活用します。これにより、最大の要素が最初に配置され、要素の不必要なシフトが回避されます。

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. ロジックを見てみる: 2 ポインタ アプローチについて説明する 面接官に明らかに。

ご質問や洞察はありますか?以下のコメント欄でシェアしてください！一緒に学びましょう。 ?

以上がLeetCode チャレンジ: ソートされた配列のマージ - JavaScript ソリューションの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。