本文共 1467 字，大约阅读时间需要 4 分钟。

题目

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。    你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6],       n = 3输出: [1,2,2,3,5,6]

来源：力扣（LeetCode）

链接：

分析

题目并不难，主要是题目中说明，最后返回的是nums1，且nums1也有足够的空间存放合并后的数组，所以在考虑时间复杂度的同时，要考虑怎么降低空间复杂度。

最简单的方法就是将nums2的值全部放到nums1中，然后对nums1排序，这种方法就不详细叙述了，这里主要采用另外两种更高效的解法。

解法一

思想：使用两个指针，分别指向nums1的头节点和nums2的头节点，对其进行比较，如果小于，这将此数组的指针后移，因为如果nums1的最小值比nums2的最小值还小，说明该最小值一定是合并数组中的最小值。

class Solution {
       public void merge(int[] nums1, int m, int[] nums2, int n) {
   		if(n!=0&&m==0){
   			System.arraycopy(nums2,0,nums1,0,n);		}		if(n!=0&&m!=0){
   			int[] nums=new int[m];//存放nums1中的数据            System.arraycopy(nums1,0,nums,0,m);			int i=0,j=0,k=0;			while(i
   

时间复杂度：O(m+n)

空间复杂度：O(m)

解法二

第一种解法，主要是需要使用额外的空间去存放nums1中已经存在的数据，所以时间复杂度为O(m)。但根据题意，nums1的空间已经足够放合并后的数组，因此第二种方法将指针从后向前遍历，充分利用nums1中无数据的一部分。

思想：因为如果nums1的最大值比nums2的最大值还大，说明该最大值一定是合并数组中的最大值。

class Solution {
       public void merge(int[] nums1, int m, int[] nums2, int n) {
       	if(n!=0&&m==0){
   			System.arraycopy(nums2,0,nums1,0,n);		}		if(n!=0&&m!=0){
   			int i=m-1,j=n-1,k=nums1.length-1;			while(i>=0&&j>=0){
   				if(nums1[i]>=nums2[j]){
   					nums1[k--]=nums1[i--];				}else{
   					nums1[k--]=nums2[j--];				}			}			while(i>=0){
   				nums1[k--]=nums1[i--];			}			while(j>=0){
   				nums1[k--]=nums2[j--];			}		}    }}

时间复杂度：O(m+n)

空间复杂度：O(1)

转载地址：http://qjebb.baihongyu.com/