Merge Sorted Array

Description

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

Notice
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.

Example
A = [1, 2, 3, empty, empty], B = [4, 5]
After merge, A will be filled as [1, 2, 3, 4, 5]

Link

Lintcode_ladder

Method

1. From back to front, compare the largest of A and B put it to the end, corrsponding move the end index "-1", and keep tracking the end of A and B
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param A: sorted integer array A which has m elements, 
     *           but size of A is m+n
     * @param B: sorted integer array B which has n elements
     * @return: void
     */
    void mergeSortedArray(int A[], int m, int B[], int n) {
        // write your code here
        // if (A && !A.empty()) {
        //     return {};
        // }
        int a = m-1;
        int b = n-1;
        int end = m+n-1;
        for (int i = end; i >= 0; --i) {
            if (a >= 0 && b >= 0) {
                A[i] = B[b] > A[a] ? B[b--]: A[a--];
            } else if (b >=0){
                A[i] = B[b--];
            }
        }
        return;
    }
};

Similar problems

x

Tags

x