## 一.題目描述  ## 二.解題技巧 這道題不存在復雜的分析過程和邊界條件。如果單純得考慮從小到大地將兩個數組進行合并的話，每次在num1中插入一個數的話，需要將后面的元素都向后移動一位，這樣，整個處理過程的時間復雜度為O(m*n)。 由于兩個數組的元素的個數是知道的，同時，合并后的數組也是遞增排序的，也就是說，排序之后的數組的最大值是放在最后面的，因此，我們可以從后往前遍歷，也就是將最大值放在第一個數組的m+n-1位置，然后將次最大值放在m+n-2位置，依次類推，這樣在將元素放置到合適位置的時候，就不需要移動元素，這個方法的時間復雜度為O(m+n)。 ## 三.示例代碼 ~~~ // 時間復雜度O(m+n)，空間復雜度O(1) class Solution { public: void merge(int A[], int m, int B[], int n) { int ia = m - 1, ib = n - 1, icur = m + n - 1; while (ia >= 0 && ib >= 0) { A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--]; } while (ib >= 0) { A[icur--] = B[ib--]; } } }; ~~~ ~~~ // 使用STL #include <iostream> #include <vector> using std::vector; class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int ResultIndex = m + n - 1; m--; n--; while (m >= 0 || n >= 0) { if (m < 0) { nums1[ResultIndex--] = nums2[n--]; continue; } if (n < 0) { nums1[ResultIndex--] = nums1[m--]; continue; } if (m >= 0 && n >= 0) { if (nums1[m] > nums2[n]) { nums1[ResultIndex--] = nums1[m--]; continue; } else { nums1[ResultIndex--] = nums2[n--]; continue; } } } } }; ~~~