LintCode 6 合并排序数组

LintCode 6 合并排序数组

题目:mergeSortedArray

要求:

合并两个排序的整数数组A和B变成一个新的数组。

样例:

给出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]

算法要求:

你能否优化你的算法，如果其中一个数组很大而另一个数组很小？

解题思路:

使用迭代器遍历2个数组，如果A的迭代器比B中的小，则存入第三个数组，并将A的迭代器迭代一次，否则将B的迭代器存入第三个数组，并将迭代器迭代一次（这里的迭代器可以理解成指针或者游标）。如果某个迭代器先迭代完成，则只需要将剩下的都存入到第三个数组中即可。

算法如下:

    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {vector<int>::iterator itA = A.begin();vector<int>::iterator itB = B.begin();vector<int> C;while (itA != A.end() && itB != B.end()) {if(*itA < *itB) {C.push_back(*itA);itA++;} else {C.push_back(*itB);itB++;}}while(itA != A.end()) {C.push_back(*itA);itA++;}while(itB != B.end()) {C.push_back(*itB);itB++;}return C;}