88、合并两个有序数组|算法(附思维导图+全部解法)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 ~