题目分析

  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即可

alt

#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的空间代价