题目分析

1. 题目首先给定键值对的个数n，然后给出n组键值对
2. 我们需要将相同的key对应的value进行合并，合并方式为value求和
3. 最终输出按照key排序的合并后的键值对结果

方法一：桶排序（空间溢出）

• 实现思路

  • 由于给定的index是有限的，所以我们考虑给每一个index一个空间计数，即申请size = 11111112大小的空间

  • 然后对每个键值对进行录入，如果key值相同则直接累计在对应的value上

  • 最后根据桶排序的索引顺序输出键值对

  • 结果是空间代价太大造成溢出

#include <iostream>
#define size 11111112								// 申请的空间大小
using namespace std;

int main() {
    int n;
    cin >> n;
    int kv[size] = {0};								// 初始化空间
    while(n) {
        int k, v;
        cin >> k;
        cin >> v;
        kv[k] += v;									// 对每一个对应的桶进行value值的装填
        n--;
    }
    
    for(int i = 0; i < size; i++) {
        if(kv[i]) cout << i << " " << kv[i] << endl;	// 根据桶排序的索引顺序输出键值对
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(n+val)O(n+val)$，遍历所有的键值对的时间代价和遍历整个桶空间的时间代价
• 空间复杂度：$O(val)O(val)$，$O(val)O(val)$级别的空间size = 11111112过大导致内存超限

方法二：红黑树

• 实现思路
  • 使用红黑树的map结构可以帮我们实现很好的排序工作，并且排序时间代价为$O(logn)O(logn)$级别
  • 同样我们构造的pair要存储key-value信息
  • 在map中我们根据key值将对应的value进行累加更新
  • 最后按照顺序输出所有的key-value即可

#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<int, int> kv;						// 声明map数据结构
    
    while(n) {
        int k, v;
        cin >> k;
        cin >> v;						    // 装填key-value信息
        kv[k] += v;							// 根据key值在value上累加
        n--;
    }
    for(auto [k, v] : kv)  {
        cout << k << " " << v << endl;		// 按照map中元素的顺序进行访问
    }

}

复杂度分析

• 时间复杂度：$O(nlogn)O(nlogn)$，遍历所有的键值对的时间开销是$O(nlogn)O(nlogn)$，但是使用map进行排序的时间开销更大，达到了$O(nlogn)O(nlogn)$
• 空间复杂度：$O(n)O(n)$，使用map的空间代价