零 标题：算法（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 历史文章 - 总览
历史文章 - 总览
刷题进度 - LeetCode：522 / 2657 、《剑指offer》：66 / 66
2 博主简介
码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专注于 一题多解、结构化思维 ，欢迎一起刷穿 LeetCode ~
