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 to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

我们可以很简单的遍历两个array就可以做出结果,这道题的重点在于我们可以利用Array A来作为output buffer从而实现不使用多余的space。因为A的最后一段n大小的空位可以用来作为buffer,所以我们只需要从A的结尾开始,一个一个扫描A和B的元素(也是从尾部开始扫描),将大的数放进A中。A中的数不会被over write因为除非B里面的元素全部填进A中也不能够over write到A的结果。

另外还要注意的是结尾,如果当第一个while循环结束时,indexA还没有为0,我们不需要继续扫描因为剩下A的结果已经是顺序的了,而如果indexB没有为0,我们则要copy所有B的元素到A中。

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        //just use A except from tail to head
        int index = m+n-1;
        int indexA = m-1;
        int indexB = n-1;
        while(indexA >= 0 && indexB >=0)
        {
            if (A[indexA] > B[indexB])
            {
                A[index--] = A[indexA--]; 
            }
            else
            {
                A[index--] = B[indexB--];
            }
        }
        
        while(indexB >= 0)
        {
            A[index--] = B[indexB--];
        }
    }
}

Shorter code, same idea, use the A as the output array, but go from right to left to avoid any overlap

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int p = m+n-1;
        int aPointer = m - 1;
        int bPointer = n - 1;
        while(p >= 0) {
            if (bPointer < 0 || (aPointer >= 0 && A[aPointer] > B[bPointer])) {
                A[p] = A[aPointer];
                aPointer--;
            }
            else {
                A[p] = B[bPointer];
                bPointer--;
            }
            p--;
        }
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s