一. 簡介

上一篇文章對"合并兩個有序數組"題目，使用了暴力解法，算法時間復雜度比較高。文章如下：

力扣網編程題：合并兩個有序數組（直接解法）-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)。