题解 | #合并表记录#

要点

选择合适的数据结构！
map/数组/哈希表

mark一下他人回答思路

这题的重点在于查找时间和存储空间的处理即数据结构的选取。
到底是map还是数组还是哈希表可以根据key的范围以及key-value对的个数选取。
1：如果key取值范围小，那么数组是最合适的。但本题不适合，因为并没有给出key的范围，如果key很大如Integer.MAX-1，那么直接开一个这么大的数组会崩的
2：如果key的取值范围很大，但是key的个数少，那么哈希表比较合适
3：如果key的取值范围很大而且key的个数很多，那么tree是比较合适的。本题目适合tree。

my code（但是性能很差

N = int(input())
table = {}
for i in range(N):
    key, value = map(int, input().split(' '))
    if key in table:
        table[key] += value
    else:
        table[key] = value
for i in sorted(table.keys()): # 按键排序，返回列表
    print(i, table[i])