如何移除vector中首元素重复的pair，保留次元素最大的条目？

直接用哈希表（unordered_map）就能高效解决这个需求，核心思路是用首元素作为键，遍历过程中始终记录每个键对应的最大次元素，最后再转成目标向量。

基础实现（不保证原顺序） #

#include <vector>
#include <unordered_map>
#include <utility>

using namespace std;

vector<pair<int, int>> keepMaxSecondElement(vector<pair<int, int>>& input) {
    unordered_map<int, int> maxMap;
    for (auto& p : input) {
        // 键不存在，或当前次元素更大时更新
        if (maxMap.find(p.first) == maxMap.end() || p.second > maxMap[p.first]) {
            maxMap[p.first] = p.second;
        }
    }
    // 转换回pair类型向量
    vector<pair<int, int>> result;
    for (auto& entry : maxMap) {
        result.emplace_back(entry.first, entry.second);
    }
    return result;
}

保留原输入中首元素的出现顺序 #

如果需要和示例输出一致，保持不同首元素的出现顺序（比如1在2前、4在5前），可以额外记录键的首次出现顺序：

#include <vector>
#include <unordered_map>
#include <utility>

using namespace std;

vector<pair<int, int>> keepMaxSecondElementWithOrder(vector<pair<int, int>>& input) {
    unordered_map<int, int> maxMap;
    vector<int> keyOrder; // 记录首元素首次出现的顺序
    for (auto& p : input) {
        if (maxMap.find(p.first) == maxMap.end()) {
            maxMap[p.first] = p.second;
            keyOrder.push_back(p.first);
        } else if (p.second > maxMap[p.first]) {
            maxMap[p.first] = p.second;
        }
    }
    // 按记录的顺序构建结果
    vector<pair<int, int>> result;
    for (int key : keyOrder) {
        result.emplace_back(key, maxMap[key]);
    }
    return result;
}

为什么set不合适？ #

set默认会按pair的整体排序规则（先比首元素，再比次元素）去重，它只会保留排序后符合规则的第一个元素，没法主动选择保留次元素最大的项，所以哈希表的方式更直接高效，时间复杂度为O(n)。

内容的提问来源于stack exchange，提问作者SHOEBILL