目錄

一、題目描述

二、初次解答

三、官方解法

四、總結

---

一、題目描述

二、初次解答

1. 思路：首次想到的解法：定義一個m+n長度的輔助數組，從頭遍歷這兩個數組，誰小就放進輔助數組中并且對應往后走，最后使用memcpy函數將輔助數組內容拷貝到nums1中。這種解法容易想到，但是空間復雜度為O(m+n)。其次想到的解法：定義三個指針i,j,k，其中i指向nums1末尾的有效位，j指向nums2的末尾，k指向nums1的m+n-1位置。循環比較nums1[i]和nums2[j]的大小，誰大就拷貝至nums1[k]并且對應指針-1。當退出循環后，將兩個數組中剩下的元素依次拷貝至nums1[k]中。

2. 代碼：對應上面的第二種解法。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int temp[m+n];int i=m-1,j=n-1,k=nums1Size-1;while(j>=0 && i>=0){if(nums2[j]>=nums1[i]){nums1[k--]=nums2[j--];}else{nums1[k--]=nums1[i--];}}while(i>=0)nums1[k--]=nums1[i--];while(j>=0)nums1[k--]=nums2[j--];
}

3. 優點：空間復雜度為O(1)且時間復雜度為O(m+n)。

4. 缺點：速度依舊不夠快。

三、官方解法

官方解法二和三分別對應上述我想到的第一種解法和第二種解法。官方解法一直接采用合并后排序的方法，調用了qsort函數。

四、總結

合并兩個有序數組，可以使用雙指針法從后往前遍歷，并將元素拷貝至目標位置。