题意: 合并两个已经排序好的数组. 这也是合并排序的最后一步操作. 还算比较简单的, 你可以从数组的两端开始. 一般来说从小到大合并会比较直观.
我们需要定义指向两个数组的下标, 每次循环就把比较小的那个数字添加到结果中即可. 当其中一个数组已经全部添加完后只需要把另一个数组剩下的元素依次添加到结果中即可.
复杂度是 O(A+B) , 其中A, B分别是两个数组的长度.
class Solution {
public:
/**
* @param A: sorted integer array A
* @param B: sorted integer array B
* @return: A new sorted integer array
*/
vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
vector<int> r;
auto a = A.size();
auto b = B.size();
r.reserve(a + b);
auto i = 0, j = 0;
while (i < a && j < b) {
if (A[i] < B[j]) { // take the smaller one
r.push_back(A[i ++]);
} else {
r.push_back(B[j ++]);
}
}
// push the remaining elements to sorted array.
for (auto k = i ; k < a; ++ k) {
r.push_back(A[k]);
}
for (auto k = j ; k < b; ++ k) {
r.push_back(B[k]);
}
return r;
}
};
英文: Coding Exercise – How to Merge Two Sorted Array?
本文一共 155 个汉字, 你数一下对不对.上一篇: PHP 是最好的语言, 但是......
下一篇: 谷歌面试扔鸡蛋问题
扫描二维码，分享本文到微信朋友圈
