题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
解题思路
解法一：双指针法
思路：
时间复杂度：O(n)
空间复杂度：O(m+n)=O(n)
解法二：直接合并后排序法
思路：直接将两个数组合并，然后再对合并后的数组进行排序
时间复杂度：平均情况O((m+n)log(m+n))
空间复杂度：平均情况O(log(m+n))
解法三：逆向双指针法
思路：从后往前对两个数组进行遍历比较，然后将较大的嵌入的nums1的后面
时间复杂度：O(m+n)
空间复杂度：O(l)
代码
解法一：双指针法（写的点冗余）
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int[] arr=new int[m+n];
int i=0;
int j=0;
int r=0;
if(m!=0 && n!=0){
while(i<m && j<n){
if((nums1[i]<=nums2[j])){
arr[r]=nums1[i];
r++;
i++;
}else{
arr[r]=nums2[j];
r++;
j++;
}
}
if(i<m){
for(;i<m;i++)
arr[r++]=nums1[i];
}
if(j<n){
for (;j<n;j++)
arr[r++]=nums2[j];
}
for(int x=0;x<m+n;x++){
nums1[x]=arr[x];
}
}else if (m==0 && n!=0){
for (int c=0;c<n;c++)
nums1[c]=nums2[c];
}else{
}
}
解法二：直接合并后排序法
public static void merge2(int[] nums1, int m, int[] nums2, int n) {
for(int i=0;i<n;i++)
nums1[m+i]=nums2[i];
Arrays.sort(nums1);
}
解法三：逆向双指针法
public static void merge3(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
cur = nums2[p2--];
} else if (p2 == -1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
