有序vector与无序vector合并排序去重的性能优化咨询

这个场景下直接粗暴合并再排序完全是浪费性能——毕竟v1已经是有序无重复的，且体量比v2大得多，咱们得利用这个核心优势来做针对性优化。

核心思路拆解 #

既然v1本身是有序无重复的，且长度远大于v2，那最优路径绝对不是把所有元素混在一起重新排序。正确的做法是：先把v2处理成有序无重复的状态，再用归并排序的合并逻辑整合两个有序数组，这样能把时间复杂度降到最低。

具体步骤&代码实现（C++） #

#include <vector>
#include <algorithm>

void merge_and_update(std::vector<int>& v1, std::vector<int>& v2) {
    // 第一步：先把v2处理成有序无重复的数组
    if (!v2.empty()) {
        std::sort(v2.begin(), v2.end());
        // 去重：把重复元素移到末尾，然后截断
        auto last_unique = std::unique(v2.begin(), v2.end());
        v2.erase(last_unique, v2.end());
    }

    // 第二步：双指针合并两个有序无重复数组，类似归并排序的合并阶段
    std::vector<int> merged;
    // 预分配足够空间，避免多次扩容带来的性能损耗
    merged.reserve(v1.size() + v2.size());
    auto it1 = v1.begin();
    auto it2 = v2.begin();

    while (it1 != v1.end() && it2 != v2.end()) {
        if (*it1 < *it2) {
            merged.push_back(*it1);
            ++it1;
        } else if (*it1 > *it2) {
            merged.push_back(*it2);
            ++it2;
        } else {
            // 两个元素相等，只保留一个（v1里已经存在）
            merged.push_back(*it1);
            ++it1;
            ++it2;
        }
    }

    // 把剩余未遍历完的元素追加进去
    merged.insert(merged.end(), it1, v1.end());
    merged.insert(merged.end(), it2, v2.end());

    // 第三步：更新v1并清空v2
    v1.swap(merged); // swap是O(1)操作，比直接赋值高效太多
    v2.clear();
}

性能优势说明 #

• 粗暴方案（直接合并后排序去重）：时间复杂度是O((m+n)log(m+n))，当m（v1长度）是n（v2长度）的1000倍时，相当于O(m log m)——这完全浪费了v1原本有序的特性，排序大数组的开销极大。
• 优化方案：时间复杂度是O(n log n + m)，因为n远小于m，n log n的开销几乎可以忽略，主要开销是线性遍历合并，性能提升非常明显。

额外细节优化 #

• 用reserve()预分配合并数组的空间，避免vector多次扩容带来的内存分配和拷贝开销。
• 用v1.swap(merged)代替直接赋值，swap操作直接交换内部指针，是O(1)的时间复杂度，比拷贝整个数组高效得多。
• 先判断v2是否为空，避免对空数组做无效操作。

内容的提问来源于stack exchange，提问作者Remi.b