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

合并两个有序的数组

1、题意重述

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组。

换句话说，即给了两个有序的数组，然后将这两个数组合并成一个有序的数组。

2、思路整理

使用双指针的思想：

Step1:首先，我们用两个指针p1，p2分别指向两个数组的头部。同时新开辟一个数组，用来存放最后的结果。

Step2：我们比较p1和p2指向值的大小，小的一个放入新开辟的数组中，同时指针向后移动。

Step3：重复step2中的操作，依次比较两个数组中的值，然后放到存储结果的数组之中。

Step4：最后，当其中一个数组遍历完之后，另一个数组则按序加入存放结果的数组之中即可。

Step5：返回存放结果的数组，输出结果。

3、代码实现

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int p1 = 0, p2 = 0;
        int[] res = new int[m + n];
        int cur;
        //循环选择,根据上述思路进行双指针遍历
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = B[p2++];
            } else if (p2 == n) {
                cur = A[p1++];
            } else if (A[p1] < B[p2]) {
                cur = A[p1++];
            } else {
                cur = B[p2++];
            }
            res[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            A[i] = res[i];
        }
    }
}

4、复杂度分析

时间复杂度：双指针，在两个数组中移动，且数组大小分别为m和n，因此时间复杂度为$O(m+n)O(m+n)$。

空间复杂度：使用res数组来保存结果，数组大小为m+n，因此空间复杂度为$O(m+n)O(m+n)$。