LeetCode 88. 合并两个有序数组

题目链接LeetCode 88. 合并两个有序数组题目描述给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数m和n分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中使合并后的数组同样按非递减顺序排列。注意最终合并后数组不应由函数返回而是存储在数组nums1中。为了应对这种情况nums1的初始长度为m n其中前m个元素表示应合并的元素后n个元素为0应忽略。nums2的长度为n。示例示例 1输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3输出[1,2,2,3,5,6]解释需要合并[1,2,3]和[2,5,6]。合并结果是[1,2,2,3,5,6]其中斜体加粗标注的为nums1中的元素。示例 2输入nums1 [1], m 1, nums2 [], n 0输出[1]解释需要合并[1]和[]。合并结果是[1]。示例 3输入nums1 [0], m 0, nums2 [1], n 1输出[1]解释需要合并的数组是[]和[1]。合并结果是[1]。注意因为m 0所以nums1中没有元素。nums1中仅存的0仅仅是为了确保合并结果可以顺利存放到nums1中。提示nums1.length m nnums2.length n0 m, n 2001 m n 200-10^9 nums1[i], nums2[j] 10^9进阶你可以设计实现一个时间复杂度为O(m n)的算法解决此问题吗题解方法一合并后排序最简洁写法思路这是最直观、代码量最少的解法。既然nums1已经预留了足够的空间我们可以直接将nums2的所有元素复制到nums1的尾部覆盖掉那些0然后直接调用系统自带的排序函数对整个nums1进行排序。复杂度分析时间复杂度O ( ( m n ) log ⁡ ( m n ) ) O((mn)\log(mn))O((mn)log(mn))复制数组耗时O ( n ) O(n)O(n)。排序耗时O ( ( m n ) log ⁡ ( m n ) ) O((mn)\log(mn))O((mn)log(mn))。总时间复杂度由排序主导。空间复杂度O ( log ⁡ ( m n ) ) O(\log(mn))O(log(mn))这是排序算法如快速排序递归调用栈所需的额外空间。代码importjava.util.Arrays;classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){// 1. 将 nums2 的元素复制到 nums1 的尾部// 从 nums2 的索引 0 开始复制 n 个元素到 nums1 的索引 m 处System.arraycopy(nums2,0,nums1,m,n);// 2. 对整个 nums1 数组进行排序Arrays.sort(nums1);}}方法二正向双指针额外空间 O(mn)思路由于两个数组已经是非递减顺序排列我们可以使用双指针分别遍历两个数组的有效部分。每次比较两个指针指向的元素将较小的元素放入临时数组中直到其中一个数组遍历完毕再将另一个数组的剩余元素追加到临时数组末尾。最后将临时数组的元素复制回nums1。这种方法类似于归并排序中的合并操作。复杂度分析时间复杂度O(m n)每个元素最多被访问一次。空间复杂度O(m n)需要额外的 ArrayList 存储合并结果。代码classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){// 合并后的总长度intlenmn;// 用于存储合并结果的临时列表ArrayListIntegernumsnewArrayList();// s1 指向 nums1 有效部分的起始位置// s2 指向 nums2 的起始位置ints10,s20;// 当两个数组都还有元素未比较时比较并放入较小的元素while(s1ms2n){if(nums1[s1]nums2[s2]){// nums1 当前元素较小或相等将其加入结果nums.add(nums1[s1]);s1;}else{// nums2 当前元素较小将其加入结果nums.add(nums2[s2]);s2;}}// 如果 nums1 还有剩余元素全部追加到结果末尾while(s1m){nums.add(nums1[s1]);s1;}// 如果 nums2 还有剩余元素全部追加到结果末尾while(s2n){nums.add(nums2[s2]);s2;}// 将合并结果复制回 nums1for(inti0;ilen;i){intnumbernums.get(i);nums1[i]number;}}}图解示例以nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3为例初始状态s10, s20 nums1(有效部分): [1, 2, 3] ↑ s1 nums2: [2, 5, 6] ↑ s2 临时数组 temp: [] --- 第1步比较 nums1[s1]1 和 nums2[s2]21 更小加入临时数组s1 nums1(有效部分): [1, 2, 3] ↑ s1 nums2: [2, 5, 6] ↑ s2 临时数组 temp: [1] 状态s11, s20 --- 第2步比较 nums1[s1]2 和 nums2[s2]2相等取 nums1s1 nums1(有效部分): [1, 2, 3] ↑ s1 nums2: [2, 5, 6] ↑ s2 临时数组 temp: [1, 2] 状态s12, s20 --- 第3步比较 nums1[s1]3 和 nums2[s2]22 更小加入临时数组s2 nums1(有效部分): [1, 2, 3] ↑ s1 nums2: [2, 5, 6] ↑ s2 临时数组 temp: [1, 2, 2] 状态s12, s21 --- 第4步比较 nums1[s1]3 和 nums2[s2]53 更小加入临时数组s1 nums1(有效部分): [1, 2, 3] ↑ s1 (s1mnums1 遍历完) nums2: [2, 5, 6] ↑ s2 临时数组 temp: [1, 2, 2, 3] 状态s13, s21 --- 第5步nums1 已遍历完将 nums2 剩余元素全部追加 nums2 剩余[5, 6] 临时数组 temp: [1, 2, 2, 3, 5, 6] --- 第6步将临时数组复制回 nums1 nums1: [1, 2, 2, 3, 5, 6] 最终结果[1, 2, 2, 3, 5, 6]方法二逆向双指针最优解空间 O(1)思路方法一需要从前往后合并因此需要额外的空间来存储结果。但题目中nums1的末尾已经预留了n个空位我们可以利用这一点从后往前进行合并。设置三个指针s1指向nums1有效元素的最后一个位置索引m-1s2指向nums2的最后一个位置索引n-1tail指向nums1的最后一个位置索引mn-1每次比较nums1[s1]和nums2[s2]将较大的元素放到nums1[tail]然后相应指针前移。由于是从后往前填充不会覆盖nums1中还未比较的元素。当nums2的元素全部放置完毕后合并完成若nums1先遍历完则只需将nums2剩余元素依次放入即可。复杂度分析时间复杂度O(m n)每个元素最多被访问一次。空间复杂度O(1)原地修改无需额外空间。代码classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){// s1 指向 nums1 有效元素的末尾ints1m-1;// s2 指向 nums2 的末尾ints2n-1;// tail 指向 nums1 的最终末尾位置inttailnm-1;// 从后往前比较将较大值放到 tail 位置while(s10s20){if(nums1[s1]nums2[s2]){// nums1 当前元素较大放到 tail 位置nums1[tail]nums1[s1];s1--;}else{// nums2 当前元素较大放到 tail 位置nums1[tail]nums2[s2];s2--;}// tail 指针前移tail--;}// 如果 nums2 还有剩余元素继续放入 nums1// 注意如果 nums1 有剩余说明它们已经在正确位置无需处理while(s20){nums1[tail]nums2[s2];s2--;tail--;}}}图解示例以nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3为例初始状态s12, s22, tail5 nums1: [1, 2, 3, 0, 0, 0] ↑ ↑ s1 tail nums2: [2, 5, 6] ↑ s2 --- 第1步nums1[s1]3 nums2[s2]66 更大放 6 到 tails2--, tail-- nums1: [1, 2, 3, 0, 0, 6] ↑ ↑ s1 tail nums2: [2, 5, 6] ↑ s2 --- 第2步nums1[s1]3 nums2[s2]55 更大放 5 到 tails2--, tail-- nums1: [1, 2, 3, 0, 5, 6] ↑ ↑ s1 tail nums2: [2, 5, 6] ↑ s2 --- 第3步nums1[s1]3 nums2[s2]23 更大放 3 到 tails1--, tail-- nums1: [1, 2, 3, 3, 5, 6] ↑ ↑ s1 tail nums2: [2, 5, 6] ↑ s2 --- 第4步nums1[s1]2 nums2[s2]2相等取 nums1 s1--, tail-- nums1: [1, 2, 2, 3, 5, 6] ↑ ↑ s1 tail nums2: [2, 5, 6] ↑ s2 --- 第5步nums1[s1]1 nums2[s2]2放 2 到 tails2--, tail-- nums1: [1, 2, 2, 3, 5, 6] ↑ s1 ↑ tail nums2: [2, 5, 6] ↑ s2 --- 第6步结束s2 0nums2 遍历完了循环结束 (此时 s10指向 nums1[0]1。因为 nums2 空了说明 nums1 剩下的元素 [1] 已经在正确位置不需要移动) 最终结果[1, 2, 2, 3, 5, 6]方法对比总结方法核心思想时间复杂度空间复杂度评价方法一合并后排序暴力拼接后调用库函数O ( ( m n ) log ⁡ ( m n ) ) O((mn)\log(mn))O((mn)log(mn))O ( log ⁡ ( m n ) ) O(\log(mn))O(log(mn))代码最短适合快速实现但效率最低。方法二正向双指针归并排序思想使用额外数组O ( m n ) O(mn)O(mn)O ( m n ) O(mn)O(mn)逻辑清晰但未做到原地修改。方法二逆向双指针利用尾部空间从后往前填O ( m n ) O(mn)O(mn)O ( 1 ) O(1)O(1)最优解面试标准答案。