Merge Two Sorted Arrays

Description

Merge two given sorted integer array A and B into a new sorted integer array.

Example
A=[1,2,3,4]
B=[2,4,5,6]
return [1,2,2,3,4,4,5,6]

Challenge
How can you optimize your algorithm if one array is very large and the other is very small?
We are here

Link

Lintcode_ladder

Method

1. create a merge func to describe how to merge two sorted arrays, with second argument(ref vector) merging into first argument(ref vector) In the main func, we can compare the size of two vector then put them into the merge func
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param A and B: sorted integer array A and B.
     * @return: A new sorted integer array
     */
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        // write your code here
        if (A.empty()) {
            return B;
        } else if (B.empty()) {
            return A;
        }
        if (A.size() >= B.size()) {
            return mergeTwo(A, B);
        } else {
            return mergeTwo(B, A);
        }
    }
    vector<int> mergeTwo(vector<int>& large, vector<int>& small) {
        int len = large.size() + small.size();
        int a = large.size() - 1;
        int b= small.size() - 1;
        // resize large to meet the total len
        large.resize(len, 0);
        // swap to sort it
        for (int i = len - 1; i >= 0; --i ) {
            if (a >= 0 && b >= 0) {
                large[i] = small[b] > large[a] ? small[b--] : large[a--];
            } else if (b >= 0) {
                large[i] = small[b--];
            }
        }
        return large;
    }
};

Similar problems

x

Tags

x