一. 简介

上一篇文章对"合并两个有序数组"题目，使用了暴力解法，算法时间复杂度比较高。文章如下：

力扣网编程题：合并两个有序数组（直接解法）-CSDN博客

本文满足进阶要求，算法时间复杂度降到 O(m+n)。使用双指针实现。

二. 力扣网编程题：合并两个有序数组（双指针解法）

 解题思路二：（双指针 / 从前往后）

进阶要求使用时间复杂度 O(m+n）的算法实现，这里可以使用双指针，遍历一遍数组。

C语言实现如下：

//双指针/从前往后
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int* nums = (int*)malloc(m*sizeof(int));int p1 = 0; //指向nums1的元素int p2 = 0; //指向nums2的元素int p = 0; //指向nums的元素memcpy(nums, nums1, m*sizeof(int));//判断边界条件while((p2 < n) && (p < m)) {if(nums[p] <= nums2[p2]) {nums1[p1] = nums[p];p++;}else {nums1[p1] = nums2[p2];p2++;}p1++;}//注意：这里一定要处理剩余的元素//处理一个数组元素排序完成，还剩下另一个数组元素的情况while(p < m) {nums1[p1] = nums[p];p++;p1++;}while(p2 < n){nums1[p1] = nums2[p2];p2++;p1++;}free(nums);nums = NULL;
}

可以看出，上面解法中，memcpy了 m个元素时间复杂度为O(m)，然后后面while时间复杂度为 O(m+n)，所以，总的时间复杂度为 O(m+n)。

解题思路三：（双指针 / 从后往前）

双指针从后往前合并的方法如下图：

解题的关键：

1. 从后向前合并：由于 nums1 后面有足够的空间，从后向前比较可以避免覆盖未处理的元素。

2. 处理剩余元素：如果 nums2 中还有剩余元素，需要将它们复制到 nums1 的前面。

3. 原地合并：不需要额外的数组空间，直接在 nums1 上进行合并操作。

C语言实现如下：

//双指针/从后前往
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int p = m+n-1; //指向准备排序数组末尾int p1 = m-1;  //指向数组nums1末尾    int p2 = n-1;  //指向数组nums2末尾while((p1 >= 0) && (p2 >= 0)) {//比较大小，最大值存入数组nums1末尾if(nums1[p1] >= nums2[p2]) {nums1[p] = nums1[p1];p1--;}else { //nums1[p1] < nums2[p2]nums1[p] = nums2[p2];p2--;}p--;}//处理剩余元素//存在一个数组nums1元素排序完成，数组nums2还有元素的情况while(p1 >= 0) {nums1[p] = nums1[p1];p1--;p--;}while(p2 >= 0) {nums1[p] = nums2[p2];p2--;p--;}
}

可以看出，这种解法的时间复杂度为 O(m+n)，空间复杂度为O(1)。