leetcode: Merge Sorted Array

leetcode Merge Sorted Array Problem Description:

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.

leetcode Merge Sorted Array  Solution and Source Code:

Test your ability to think out of box. Just a very little change of the regular merge sort. For this problem, we start from the largest number in the two sorted arrays and put the larger one into the tail of array A. Essentially, this is the same as regular merger sort. The following is the accepted source code:

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int current = m + n - 1, i = m - 1, j = n -1;
		while (i >= 0 && j >= 0) {
			if (A[i] > B[j]) {
				A[current--] = A[i--];
			}
			else
				A[current--] = B[j--];
		}
		while (i >= 0) A[current--] = A[i--];
		while (j >= 0) A[current--] = B[j--];
    }
};

leetcode Merge Sorted Array  Tips and Remarks:

If you stuck at some point thinking about the tricky solution, then a better option would be start over and try to think out of box (e.g., reverse way). Usually, the solution is not as complex as you think, it is often very simple with short and elegant code.

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on April 27, 2013