LeetCode --- 88. Merge Sorted Array

題目連結：Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:

You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

這道題的要求是将有序數組B合并到有序數組A中，假設A有足夠空間容納B中所有元素。

歸并排序中合并的步驟，不過由于是要合并到A中，也就是不申請額外空間，是以，為了減少移動A重元素的次數，考慮從後往前逐漸合并：從後往前周遊A和B數組，每次把大的數字從A中m+n位置逐漸往前放。

時間複雜度：O(m+n)

空間複雜度：O(1)

1 class Solution
 2 {
 3 public:
 4     void merge(int A[], int m, int B[], int n)
 5     {
 6         int i = m - 1, j = n - 1, k = m + n - 1;
 7         while(j >= 0)
 8         {
 9             if(i >= 0 && A[i] > B[j])
10                 A[k --] = A[i --];
11             else
12                 A[k --] = B[j --];
13         }
14     }
15 };
           

轉載請說明出處：LeetCode --- 88. Merge Sorted Array