VIRTUALS

the virtual labs for the virtuals

0%

HJ8. 合并表记录

Posted on Edited on In , , ,

摘要：
有序哈希表的应用。

题目

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

输入描述：
先输入键值对的个数
然后输入成对的 index 和 value 值，以空格隔开

输出描述：
输出合并后的键值对（多行）

示例1

输入：
4
0 1
0 2
1 2
3 4

输出：
0 3
1 2
3 4

有序哈希表

将数据放到哈希表中，再将 key 相同的 value 累加即可。同时，题目要求按照 key 升序排列。所以可以考虑使用有序哈希表。
在C++中是STL的 Map，在Java中则是 TreeMap。

注意在Java中 Map.Entry<K, V> 是Map的静态接口。遍历的时候用到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * author: etoa
 * 2021-08-16 22:06:45
 */
#include <bits/stdc++.h>

using namespace std;

int main()
{
    map<int, int> hash;
    int n;
    cin >> n;
    for (; n--;) {
        int x, y;
        cin >> x >> y;
        hash[x] += y;
    }
    for (auto [key, value] : hash) {
        cout << key << ' ' << value << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
 * author: etoa
 * 2021-08-16 22:30:00
 */
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Map<Integer, Integer> hash = new TreeMap<>();
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            if (hash.containsKey(x)) {
                hash.put(x, hash.get(x) + y);
            } else {
                hash.put(x, y);
            }
        }
        for (Map.Entry<Integer, Integer> entry : hash.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
}

原题链接： HJ8. 合并表记录