4、合并两个有序数组

1、地址

https://leetcode-cn.com/problems/merge-sorted-array/

2、题面分析

题目

题目信息

• 无需返回值
• 答案要在问题的输入上进行修改

• m + n > 0 表示着返回一定是有意义的

  3、暴力破解

  代码实现（内置排序方法）（不推荐）

  class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
         for(int i = 0; i < n; i++){
             nums1[m + i] = nums2[i]; 
         }
        Arrays.sort(nums1);
    }
  }

  代码实现（插入排序）

  ```java public class Solution {

  public void merge(int[] nums1, int m, int[] nums2, int n) {

    if (n == 0) {
        return;
    }
    int i = 0;
    int j = 0;
    int count = m;
    // nums2插入完成 或者 没有需要移动的nums1时结束
    while (count > 0 && j < n) {
        if (nums2[j] < nums1[i]) {
            for (int k = i + count - 1; k >= i; k--) {
                nums1[k + 1] = nums1[k];
            }
            nums1[i] = nums2[j];
            j++;
        } else {
            count--;
        }
        i++;
    }
    if (j < n) {
        count = m + j;
        for (int k = j; k < n; k++) {
            nums1[count++] = nums2[k];
        }
    }

  } }

<a name="VeWYL"></a>
## 4、顺序归并
<a name="VHZvR"></a>
#### 代码实现
```java
public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] result = new int[m + n];
        int i = 0;
        int j = 0;
        int tail = 0;
        while(i < m && j < n ){
            if(nums1[i] <= nums2[j]){
                result[tail++] = nums1[i++];
            }else{
                result[tail++] = nums2[j++];
            }
        }
        while(i < m){
           result[tail++] = nums1[i++];
        }
        while(j < n){
           result[tail++] = nums2[j++];
        }
        for(int k = 0; k < m + n; k++){
            nums1[k] = result[k];
        }
    }
}

5、逆序归并

代码实现

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int tail = m + n -1;
        while(j >= 0 && i >= 0){
            if(nums2[j] >= nums1[i]){
                nums1[tail--] = nums2[j--];
            }else{
                nums1[tail--] = nums1[i--];
            }
        }
        if(j >= 0){
            for(int k = 0; k <= j; k++){
                nums1[k] = nums2[k];
            }
        }
    }
}