C++两个有序vector的合并的高效算法
时间: 2023-09-11 13:08:14 浏览: 39
可以使用归并排序的思想,将两个有序的vector合并成一个有序的vector。
具体步骤如下:
1. 定义两个指针分别指向两个vector的首元素,比较两个指针所指的元素大小。
2. 将较小的元素加入结果vector,并将指向该元素的指针向后移动一位。
3. 重复步骤2,直到其中一个vector的指针指向了最后一个元素。
4. 将另一个vector剩余的元素全部加入结果vector。
5. 返回结果vector。
代码实现如下:
```c++
vector<int> merge(vector<int>& a, vector<int>& b) {
vector<int> res;
int i = 0, j = 0;
while (i < a.size() && j < b.size()) {
if (a[i] < b[j]) {
res.push_back(a[i]);
i++;
} else {
res.push_back(b[j]);
j++;
}
}
while (i < a.size()) {
res.push_back(a[i]);
i++;
}
while (j < b.size()) {
res.push_back(b[j]);
j++;
}
return res;
}
```
该算法的时间复杂度为O(n),其中n为两个vector的元素总数。