题意概述

• 给定两个有序数组
• 要求将两个数组合并为一个有序升序数组

方法一：暴力

思路与具体做法

将数组B放进数组A的尾部，然后对整个数组排序即可

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
		for(int i=0;i<n;i++){//合并后直接排序 
			A[m+i]=B[i];
		} 
		sort(A,A+n+m);
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(\right(m+n\left)2_{}m+n\right)O((m+n)\backslash log\_\{2\}\{m+n\}\; )$O((m+n)log2​m+n)，对长度为$(m+n)(m+n)$(m+n)的数组sort排序，排序时间复杂度$O\left(\right(m+n\left)2_{}m+n\right)O((m+n)\backslash log\_\{2\}\{m+n\}\; )$O((m+n)log2​m+n)
• 空间复杂度：$O\left(2_{}m+n\right)O(\backslash log\_\{2\}\{m+n\}\; )$O(log2​m+n)， 对长度为$(m+n)(m+n)$(m+n)的数组sort排序

方法二：双指针

思路与具体做法

• 类比归并排序的“合并”步骤，将两个有序数组有序地放进一个新数组里
• 为两个数组AB分别设一个指针p1，p2来作为当前比较的元素
• 在两数组公共长度内，将较小的元素放入ans数组，并令新数组，所取元素的数组，各指针加1，接着比较下一元素，直到比较完所有公共部分元素
• 最后数组AB可能会剩余一个指针未走到尾，将其全部加入ans数组即可

	class Solution {
	public:
	    void merge(int A[], int m, int B[], int n) {
	        int p=0,q=0;//两个指针p,q分别指向AB数组中当前对比元素 
	        int ans[m+n];
	        int cn=0; 
	        while(p<m&&q<n){//在AB数组的公共部分进行对比，小的加入ans数组 
	        	if(A[p]<B[q])ans[cn++]=A[p++];
				else ans[cn++]=B[q++];
			}
			while(p<m)ans[cn++]=A[p++];//有剩余的则放入ans数组尾部 
			while(q<n)ans[cn++]=B[q++];
			for(int i=0;i<m+n;i++){//写回A数组 
				A[i]=ans[i];
			}
	    }
	};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(m+n)O(m+n)$O(m+n)，指针依次遍历长度$(m+n)(m+n)$(m+n)的数组
• 空间复杂度：$O(m+n)O(m+n)$O(m+n)，需要用到长度为$(m+n)(m+n)$(m+n)的辅助数组