Monday, November 17, 2014

[LeetCode] 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 andn respectively.
思路:
直观思路显然是双指针i, j同时扫描A, B,选min(A[i], B[j])作为下一个元素插入。但是只能利用A后面的空间来插入,这样就很不方便了。
反向思路,merge后的数组一共有m+n个数。i, j从A, B尾部扫描,选max(A[i], B[j])插入从m+n起的尾部。这样也可以防止插入到A原来数字的范围内时,overwrite掉A原来的数。


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

4 comments:

  1. 思路清晰!
    ```
    while(pa>=0) A[pc--] = A[pa--];
    ```
    这一行是不是可以去掉?因为A上做的in place change.

    ReplyDelete
  2. 是的。这行while(pa>=0) A[pc--] = A[pa--];可以去掉, 因为是把数组B放到A里。如果 A里还有元素没有扫描到, 表明B里的元素全都扫描到了, 那么A里这些剩下的元素不用动位置了, 已经是排好序的并且都小于B里的最小值了。

    ReplyDelete