题解 | #合并两个有序的数组#

暴力求解

import java.util.*;
public 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];
        }
        Arrays.sort(A);
        
    }
}

时间复杂度：O((m+n)log(m+n))。 排序序列长度为m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log(m+n))。

空间复杂度：O(log(m+n))。 排序序列长度为m+n，套用快速排序的空间复杂度即可，平均情况为 O(log(m+n))。 逆向双指针

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int l1 = m-1;
        int l2 = n-1;
        int p=m+n-1;
        
        while(l1>=0&&l2>=0){
            A[p--] =A[l1]>B[l2]?A[l1--]:B[l2--];
        }
        for(int i=0;i<=l2;i++){
            A[i] = B[i];
        }
        
    }
}

时间o（m+n） 空间o（1）