乐趣区

关于javascript:88合并两个有序数组-算法leetcode附思维导图-全部解法300题

零 题目:算法(leetcode,附思维导图 + 全副解法)300 题之(88)合并两个有序数组

一 题目形容


二 解法总览(思维导图)

三 全副解法

1 计划 1

1)代码:

// 计划 1“本人。(忽视题目要求)”。// 思路:// 1)状态初始化预处理 nums1(即 nums1.splice(m))和 nums2(即 nums2.splice(n))。// 该操作均使得 nums1、nums2 产生扭转,扭转原数组!!// 2)合并:将 nums2 并入 nums1 中。// 3)返回后果:将 nums1 升序并返回。var merge = function(nums1, m, nums2, n) {// 1)状态初始化预处理 nums1(即 nums1.splice(m))和 nums2(即 nums2.splice(n))。// 该操作均使得 nums1、nums2 产生扭转,扭转原数组!!nums1.splice(m);
    nums2.splice(n);
    
    // 2)合并:将 nums2 并入 nums1 中。nums1.push(...nums2);
    
    // 3)返回后果:将 nums1 升序并返回。return nums1.sort((a,b) => a-b);
};

2 计划 2

1)代码:

// 计划 2“本人。双指针 + 额定数组法”。// 技巧:“既然要求工夫复杂度为 O(m + n),那么咱们能够通过 空间 来换 工夫”。// 思路:// 1)状态初始化:nums1Index = 0, nums2Index = 0, sortedList = []。// 2)循环解决,条件为 nums1Index < m && nums2Index < n。// 2.1)若 nums1Val <= nums2Val,则 sortedList.push(nums1Val); nums1Index++。// 2.2)若 nums1Val > nums2Val,则 sortedList.push(nums2Val); nums2Index++。// 3)边界:可能有一边还有残余,将它们放入 sortedList 中。// 4)遍历 sortedList,顺次笼罩 nums1 上的值。var merge = function(nums1, m, nums2, n) {// 1)状态初始化:nums1Index = 0, nums2Index = 0, sortedList = []。let nums1Index = 0,
        nums2Index = 0,
        sortedList = [];

    // 2)循环解决,条件为 nums1Index < m && nums2Index < n。while (nums1Index < m && nums2Index < n) {const nums1Val = nums1[nums1Index],
            nums2Val = nums2[nums2Index];
        
        // 2.1)若 nums1Val <= nums2Val,则 sortedList.push(nums1Val); nums1Index++。if (nums1Val <= nums2Val) {sortedList.push(nums1Val);
            nums1Index++;
        }
        // 2.2)若 nums1Val > nums2Val,则 sortedList.push(nums2Val); nums2Index++。else {sortedList.push(nums2Val);
            nums2Index++;
        }
    }

    // 3)边界:可能有一边还有残余,将它们放入 sortedList 中。if (nums1Index === m) {sortedList.push(...nums2.slice(nums2Index));
    }
    else if (nums2Index === n) {sortedList.push(...nums1.slice(nums1Index));
    }

    // 4)遍历 sortedList,顺次笼罩 nums1 上的值。for (let i = 0; i < (m + n); i++) {nums1[i] = sortedList[i];
    }
}

3 计划 3

1)代码:

// 计划 3“逆向指针法”。// 参考:// 1)https://leetcode.cn/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/

// 思路:// 1)状态初始化:nums1Index = m - 1, 
// nums2Index = n - 1, fillIndex = m + n - 1。// 2)外围:循环解决,条件为 nums1Index >= 0 || nums2Index >= 0。// 2.1)若 nums1 已“用完”(即 nums1Index === -1),// 则 fillVal = nums2Val; nums2Index--;。// 2.2)若 nums2 已“用完”(即 nums2Index === -1),// 则 fillVal = nums1Val; nums1Index--;。// 2.3)若 nums1Val > nums2Val,// 则 fillVal = nums1Val; nums1Index--;。// 2.4)若 nums1Val <= nums2Val,// 则 fillVal = nums2Val; nums2Index--;。// 2.5)nums1[fillIndex] = fillVal; fillIndex--;。var merge = function(nums1, m, nums2, n) {
    // 1)状态初始化:nums1Index = m - 1, 
    // nums2Index = n - 1, fillIndex = m + n - 1。let nums1Index = m - 1,
        nums2Index = n - 1,
        fillIndex = m + n - 1;
    
    // 2)外围:循环解决,条件为 nums1Index >= 0 || nums2Index >= 0。while (nums1Index >= 0 || nums2Index >= 0) {const nums1Val = nums1[nums1Index],
            nums2Val = nums2[nums2Index];
        let fillVal;
        
        // 2.1)若 nums1 已“用完”(即 nums1Index === -1),// 则 fillVal = nums2Val; nums2Index--;。if (nums1Index === -1) {
            fillVal = nums2Val;
            nums2Index--
        }
        // 2.2)若 nums2 已“用完”(即 nums2Index === -1),// 则 fillVal = nums1Val; nums1Index--;。else if (nums2Index === -1) {fillVal = nums1[nums1Index];
            nums1Index--;
        }
        // 2.3)若 nums1Val > nums2Val,// 则 fillVal = nums1Val; nums1Index--;。else if (nums1Val > nums2Val) {
            fillVal = nums1Val;
            nums1Index--;
        }
        // 2.4)若 nums1Val <= nums2Val,// 则 fillVal = nums2Val; nums2Index--;。else {
            fillVal = nums2Val;
            nums2Index--;
        }

        // 2.5)nums1[fillIndex] = fillVal; fillIndex--;。nums1[fillIndex] = fillVal;
        fillIndex--;
    }
}

四 资源分享 & 更多

1 历史文章 – 总览

2 博主简介

码农三少,一个致力于编写 极简、但齐全题解(算法 )的博主。
专一于 一题多解、结构化思维,欢送一起刷穿 LeetCode ~

退出移动版