题解|HJ8 合并表记录

题目链接|合并表记录

数据表记录包含表索引和数值（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。

方法一：利用python中的字典进行模拟求解 （哈希表）

使用python下的dict（C++/C中可以使用map/unordered_map达到相似的效果）对相同索引下的记录数字进行相加后输出。

时间复杂度:$O(Nlog(N))O(Nlog(N))$，解释：需要对所有输入的操作进行处理，时间复杂度$O(N)O(N)$，排序时间复杂度$O(Nlog(N))O(Nlog(N))$。

空间复杂度:$O(N)O(N)$，解释：需要$O(N)O(N)$个字典存储输入的数据。

n = int(input()) 
record = {} #python里的map更加方便
for i in range(n):
    line = input().split()
    idx = int(line[0]) #当前记录的索引值
    value = int(line[1]) #当前记录的数值
    record[idx] = record.get(idx,0)+value #将record中对应索引值的原有累积value加上当前记录的value
for idx in sorted(record): #对记录表进行排序并输出
    print(idx, record[idx])

方法二：利用C++/C中的unordered_map进行数据合并（哈希表）

利用C++/C中的unordered_map创建数值类型为<int, int>的哈希表，第一维表示记录的index，第二维表示记录的value。index可以使用STL中的set存储（因为STL中的set会对插入的元素进行自动去重和从小到大的排序）。当输入新的数据记录时，将其value和哈希表中对应index的原value进行相加。处理完后按照set中的index顺序输出哈希表中的index以及对应的合并好的value。

时间复杂度:$O(Nlog(N))O(Nlog(N))$，解释：输入记录的复杂度为$O(N)O(N)$，利用set进行键值排序及去重的复杂度为$O(Nlog(N))O(Nlog(N))$，所以最后复杂度为$O(Nlog(N))O(Nlog(N))$。

空间复杂度:$O(N)O(N)$，解释：需要$O(N)O(N)$个unordered_map存储输入的数据，利用set处理index所需要的的空间为$O(N)O(N)$。

#include <cstring>
#include <cstdio>
#include <set>
#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    while(cin >> n) {
        unordered_map<int, int> rec; //创建一个哈希表储存记录
        set<int> temp;
        for(int i = 0; i < n; i++) {
            int idx, val;
            cin >> idx >> val;
            rec[idx] += val; //对于key相同的record，合并value
            temp.insert(idx); //使用set对index进行记录
        }
        for(auto i : temp) {
            cout << i << " " << rec[i] << "\n";
        }
    }
    return 0;
}