Skip to content

Latest commit

 

History

History
236 lines (187 loc) · 5.92 KB

88.merge-sorted-array.md

File metadata and controls

236 lines (187 loc) · 5.92 KB

题目地址（88. 合并两个有序数组）

https://leetcode-cn.com/problems/merge-sorted-array/

题目描述

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例: 输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • loomberg
  • facebook
  • microsoft

前置知识

  • 归并排序

思路

符合直觉的做法是将nums2插到num1的末尾, 然后排序

具体代码：

// 这种解法连m都用不到// 这显然不是出题人的意思if(n===0)return;letcurrent2=0;for(leti=nums1.length-1;i>=nums1.length-n;i--){nums1[i]=nums2[current2++];}nums1.sort((a,b)=>a-b);// 当然你可以自己写排序，这里懒得写了，因为已经偏离了题目本身

这道题目其实和基本排序算法中的merge sort非常像。

我们先来回顾一下 merge sort 的 merge 过程。merge 的过程可以是先比较两个数组的头元素，然后将较小的推到最终的数组中，并将其从原数组中出队列。不断循环直到两个数组都为空。

具体代码如下：

// 将nums1 和 nums2 合并functionmerge(nums1,nums2){letret=[];leti=(j=0);while(i<nums1.length||j<nums2.length){if(i===nums1.length){ret.push(nums2[j]);j++;continue;}if(j===nums2.length){ret.push(nums1[i]);i++;continue;}consta=nums1[i];constb=nums2[j];if(a>b){ret.push(nums2[j]);j++;}else{ret.push(nums1[i]);i++;}}returnret;}

但是 merge sort 很多时候，合并的时候我们通常是新建一个数组，但是这道题目要求的是原地修改.这就和 merge sort 的 merge 过程有点不同。这里要求原地修改。如果使用类似上面的方法，如果采用从头开始遍历，需要将 nums1 的前 m 个数组放到另一个数组中避免写指针写入的干扰。 这样空间复杂度就是 $O(m)$。其实我们能只要从后往前比较，并从后往前插入即可。

我们需要三个指针：

  1. 写指针 current， 用于记录当前填补到那个位置了

  2. m 用于记录 nums1 数组处理到哪个元素了

  3. n 用于记录 nums2 数组处理到哪个元素了

如图所示：

  • 灰色代表 num2 数组已经处理过的元素
  • 红色代表当前正在进行比较的元素
  • 绿色代表已经就位的元素

88.merge-sorted-array-188.merge-sorted-array-288.merge-sorted-array-3

关键点解析

  • 从后往前比较，并从后往前插入，这样可避免写指针影响，同时将空间复杂度降低到 $O(1)$

代码

代码支持：Python3, C++, Java, JavaScript

JavaSCript Code:

varmerge=function(nums1,m,nums2,n){// 设置一个指针，指针初始化指向nums1的末尾（根据#62，应该是index为 m+n-1 的位置，因为nums1的长度有可能更长）// 然后不断左移指针更新元素letcurrent=m+n-1;while(current>=0){// 没必要继续了if(n===0)return;// 为了方便大家理解，这里代码有点赘余if(m<1){nums1[current--]=nums2[--n];continue;}if(n<1){nums1[current--]=nums1[--m];continue;}// 取大的填充 nums1的末尾// 然后更新 m 或者 nif(nums1[m-1]>nums2[n-1]){nums1[current--]=nums1[--m];}else{nums1[current--]=nums2[--n];}}};

C++ code:

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int current = m + n - 1; while (current >= 0) { if (n == 0) return; if (m < 1) { nums1[current--] = nums2[--n]; continue; } if (n < 1) { nums1[current--] = nums1[--m]; continue; } if (nums1[m - 1] > nums2[n - 1]) nums1[current--] = nums1[--m]; else nums1[current--] = nums2[--n]; } } };

Java Code:

classSolution { publicvoidmerge(int[] nums1, intm, int[] nums2, intn) { inti=m-1, j=n-1, k=m+n-1; // 合并while(i>=0 && j>=0) { if(nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } // 合并剩余的nums2while(j>=0) { nums1[k--] = nums2[j--]; } } }

Python Code:

classSolution: defmerge(self, nums1: List[int], m: int, nums2: List[int], n: int) ->None: """ Do not return anything, modify nums1 in-place instead. """pos=m+n-1whilem>0andn>0: ifnums1[m-1] <nums2[n-1]: nums1[pos] =nums2[n-1] n-=1else: nums1[pos] =nums1[m-1] m-=1pos-=1whilen>0: nums1[pos] =nums2[n-1] n-=1pos-=1

复杂度分析

  • 时间复杂度：$O(M + N)$
  • 空间复杂度：$O(1)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

close