|
| 1 | +##题目地址 |
| 2 | + |
| 3 | +https://leetcode.com/problems/merge-sorted-array/description/ |
| 4 | + |
| 5 | +##题目描述 |
| 6 | + |
| 7 | +``` |
| 8 | +Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. |
| 9 | +
|
| 10 | +Note: |
| 11 | +
|
| 12 | +The number of elements initialized in nums1 and nums2 are m and n respectively. |
| 13 | +You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. |
| 14 | +Example: |
| 15 | +
|
| 16 | +Input: |
| 17 | +nums1 = [1,2,3,0,0,0], m = 3 |
| 18 | +nums2 = [2,5,6], n = 3 |
| 19 | +
|
| 20 | +Output: [1,2,2,3,5,6] |
| 21 | +``` |
| 22 | + |
| 23 | +##思路 |
| 24 | + |
| 25 | +符合直觉的做法是`将nums2插到num1的末尾, 然后排序` |
| 26 | + |
| 27 | + |
| 28 | +具体代码： |
| 29 | + |
| 30 | +```js |
| 31 | +// 这种解法连m都用不到 |
| 32 | +// 这显然不是出题人的意思 |
| 33 | +if (n===0)return; |
| 34 | +let current2=0; |
| 35 | +for(let i=nums1.length-1; i>=nums1.length- n ; i--) { |
| 36 | + nums1[i]= nums2[current2++]; |
| 37 | + } |
| 38 | +nums1.sort((a,b)=> a- b);// 当然你可以自己写排序，这里懒得写了，因为已经偏离了题目本身 |
| 39 | + |
| 40 | +``` |
| 41 | + |
| 42 | +这道题目其实和基本排序算法中的`merge sort`非常像，但是 merge sort 很多时候，合并的时候我们通常是 |
| 43 | +新建一个数组，这样就很简单。 但是这道题目要求的是`原地修改`. |
| 44 | + |
| 45 | +这就和 merge sort 的 merge 过程有点不同，我们先来回顾一下 merge sort 的 merge 过程。 |
| 46 | + |
| 47 | +merge 的过程`可以`是先比较两个数组的头元素，然后将较小的推到最终的数组中，并将其从原数组中出队列。 |
| 48 | +循环直到两个数组都为空。 |
| 49 | + |
| 50 | +具体代码如下： |
| 51 | + |
| 52 | +```js |
| 53 | +// 将nums1 和 nums2 合并 |
| 54 | +functionmerge(nums1,nums2) { |
| 55 | +let ret= []; |
| 56 | +while (nums1.length||nums2.length) { |
| 57 | +// 为了方便大家理解，这里代码有点赘余 |
| 58 | +if (nums1.length===0) { |
| 59 | +ret.push(nums2.shift()); |
| 60 | +continue; |
| 61 | + } |
| 62 | + |
| 63 | +if (nums2.length===0) { |
| 64 | +ret.push(nums1.shift()); |
| 65 | +continue; |
| 66 | + } |
| 67 | +consta= nums1[0]; |
| 68 | +constb= nums2[0]; |
| 69 | +if (a> b) { |
| 70 | +ret.push(nums2.shift()); |
| 71 | + }else { |
| 72 | +ret.push(nums1.shift()); |
| 73 | + } |
| 74 | + } |
| 75 | +return ret; |
| 76 | +} |
| 77 | +``` |
| 78 | + |
| 79 | +这里要求原地修改，其实我们能只要从后往前比较，并从后往前插入即可。 |
| 80 | + |
| 81 | +我们需要三个指针： |
| 82 | + |
| 83 | +1. current 用于记录当前填补到那个位置了 |
| 84 | + |
| 85 | +2. m 用于记录 nums1 数组处理到哪个元素了 |
| 86 | + |
| 87 | +3. n 用于记录 nums2 数组处理到哪个元素了 |
| 88 | + |
| 89 | +如图所示： |
| 90 | + |
| 91 | +- 灰色代表 num2 数组已经处理过的元素 |
| 92 | +- 红色代表当前正在进行比较的元素 |
| 93 | +- 绿色代表已经就位的元素 |
| 94 | + |
| 95 | + |
| 96 | + |
| 97 | + |
| 98 | + |
| 99 | +##关键点解析 |
| 100 | + |
| 101 | +- 从后往前比较，并从后往前插入 |
| 102 | + |
| 103 | +##代码 |
| 104 | + |
| 105 | +```js |
| 106 | +/* |
| 107 | + * @lc app=leetcode id=88 lang=javascript |
| 108 | + * |
| 109 | + * [88] Merge Sorted Array |
| 110 | + * |
| 111 | + * https://leetcode.com/problems/merge-sorted-array/description/ |
| 112 | + * |
| 113 | + * algorithms |
| 114 | + * Easy (34.95%) |
| 115 | + * Total Accepted: 347.5K |
| 116 | + * Total Submissions: 984.7K |
| 117 | + * Testcase Example: '[1,2,3,0,0,0]\n3\n[2,5,6]\n3' |
| 118 | + * |
| 119 | + * Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as |
| 120 | + * one sorted array. |
| 121 | + * |
| 122 | + * Note: |
| 123 | + * |
| 124 | + * |
| 125 | + * The number of elements initialized in nums1 and nums2 are m and n |
| 126 | + * respectively. |
| 127 | + * You may assume that nums1 has enough space (size that is greater or equal to |
| 128 | + * m + n) to hold additional elements from nums2. |
| 129 | + * |
| 130 | + * |
| 131 | + * Example: |
| 132 | + * |
| 133 | + * |
| 134 | + * Input: |
| 135 | + * nums1 = [1,2,3,0,0,0], m = 3 |
| 136 | + * nums2 = [2,5,6], n = 3 |
| 137 | + * |
| 138 | + * Output: [1,2,2,3,5,6] |
| 139 | + * |
| 140 | + * |
| 141 | +*/ |
| 142 | +/** |
| 143 | + *@param{number[]}nums1 |
| 144 | + *@param{number}m |
| 145 | + *@param{number[]}nums2 |
| 146 | + *@param{number}n |
| 147 | + *@return{void} Do not return anything, modify nums1 in-place instead. |
| 148 | +*/ |
| 149 | +varmerge=function(nums1,m,nums2,n) { |
| 150 | +// 设置一个指针，指针初始化指向nums1的末尾 |
| 151 | +// 然后不断左移指针更新元素 |
| 152 | +let current=nums1.length-1; |
| 153 | + |
| 154 | +while (current>=0) { |
| 155 | +// 没必要继续了 |
| 156 | +if (n===0)return; |
| 157 | + |
| 158 | +// 为了方便大家理解，这里代码有点赘余 |
| 159 | +if (m<0) { |
| 160 | + nums1[current--]= nums2[--n]; |
| 161 | +continue; |
| 162 | + } |
| 163 | + |
| 164 | +if (n<0) { |
| 165 | + nums1[current--]= nums1[--m]; |
| 166 | +continue; |
| 167 | + } |
| 168 | +// 取大的填充 nums1的末尾 |
| 169 | +// 然后更新 m 或者 n |
| 170 | +if (nums1[m-1]> nums2[n-1]) { |
| 171 | + nums1[current--]= nums1[--m]; |
| 172 | + }else { |
| 173 | + nums1[current--]= nums2[--n]; |
| 174 | + } |
| 175 | + } |
| 176 | +}; |
| 177 | +``` |
