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

解法一：合并后排序

思路步骤：

• 对原数组A,B进行合并
• 将合并后的数组A进行排序
• 

  java参考代码：

  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);
     }
  }

  复杂度分析：

  时间复杂度：(平均情况)
  排序序列长度为 m+n，套用快速排序的时间复杂度即可，所以平均时间复杂度为：
  空间复杂度：(平均情况) 排序序列长度为 m+n，套用快速排序的时间复杂度即可
  ，因此空间复杂度的平均情况为：

  解法二：双指针

  思路步骤

• 这一方法将两个数组看作队列
• 每次从两个数组头部取出比较小的数字放到结果中。
• 参考图解：

Java参考代码：

import java.util.*;
public class Solution