机试题——通讯录归并

题目描述

你有一个通讯录，每个联系人包含姓名和手机号，一个联系人大概有多个手机号。假如两个联系人拥有相同的手机号，我们以为他们是同一个人。任务是整理通讯录，将具有相同手机号的联系人归并为一个联系人，并返回归并后的通讯录列表。假如归并时发现联系人姓名差别，以字典序小的为姓名。
输入描述

• 第一行：一个整数num，表示通讯录的记录数量（1 <= num <= 1000）。
  
• 接下来num行：每行表示一条联系人记录，包含姓名和多少电话号码（电话号码个数不超过10，长度在1到10之间）。姓名由英文字母大小写构成，长度在1到10之间。
  

输出描述

整理后的通讯录列表，此中具有相同手机号的联系人归并为一个联系人。输出联系人姓名和手机号码列表按ASCII码升序排序。
用例输入

1. 4
2. kaka 10000000000 10000000001
3. tata 10000000020
4. kaka 10000000000 10000000002
5. tata 10000000010

复制代码

1. kaka 10000000000 10000000001 10000000002
2. tata 10000000010
3. tata 10000000020

复制代码

第一个kaka和第二个kaka有相同的手机号10000000000，因此他们被视为同一个人。归并后的手机号按ASCII码升序排序。

1. 3
2. kaka 10000000000 10000000001
3. kaka 10000000001 10000000002
4. kaka 10000000002 10000000003

复制代码

1. kaka 10000000000 10000000001 10000000002 10000000003

复制代码

第一个kaka和第二个kaka有相同的手机号10000000001，第二个kaka和第三个kaka有相同的手机号10000000002，因此他们被视为同一个人。归并后的手机号按ASCII码升序排序。
解题思路

• 题目建模：
  
  
  
  • 使用并查集来归并具有相同手机号的联系人。
    
  • 使用哈希表记录每个手机号对应的联系人索引。
    
  • 使用集合去重并排序手机号。
    
  
  
• 并查集：
  
  
  
  • 对于每个联系人的手机号，假如该手机号已经出现过，则将当前联系人与之前出现的联系人归并。
    
  • 使用路径压缩优化并查集。
    
  
  
• 归并联系人：
  
  
  
  • 对于每个联系人，找到其根节点（即归并后的代表）。
    
  • 归并手机号，去重并排序。
    
  • 假如姓名差别，选择字典序小的姓名。
    
  
  
• 输出结果：
  
  
  
  • 按姓名和手机号的ASCII码升序排序，输出归并后的通讯录。
    
  
  

代码

1. #include<iostream>
2. #include<cstdio>
3. #include<cstring>
4. #include<cmath>
5. #include<map>
6. #include<algorithm>
7. #include<string>
8. #include<vector>
9. #include<unordered_map>
10. #include<unordered_set>
11. #include<queue>
12. #include<set>
13. #include<list>
14. #include<sstream>
15. #include<bitset>
16. #include<stack>
17. #include<climits>
18. #include<iomanip>
19. #include<cstdint>
20. using namespace std;
22. // 并查集
23. vector<int> f(10005);
24. int find(int x) {
25.     if (f[x] == x) return x;
26.     else return f[x] = find(f[x]);
27. }
28. void un(int x, int y) {
29.     int fx = find(x);
30.     f[fx] = y;
31. }
33. int main() {
34.     ios::sync_with_stdio(false);  // 关闭与 C 的同步
35.     cin.tie(nullptr);             // 解除 cin 与 cout 的绑定
36.     int n;
37.     cin >> n;
38.     cin.ignore();
39.     vector<string> name(n);
40.     vector<vector<string>> phone(n);
41.     map<string, int> memo; // 记录手机号对应的联系人索引
42.     for (int i = 0; i < n; i++) {
43.         f[i] = i; // 初始化并查集
44.         string input, temp;
45.         getline(cin, input);
46.         istringstream is(input);
47.         is >> name[i];
48.         while (is >> temp) {
49.             if (memo.count(temp)) { // 如果手机号已经出现过
50.                 un(memo[temp], i); // 合并两个联系人
51.             }
52.             memo[temp] = i; // 更新手机号对应的联系人索引
53.             phone[i].push_back(temp); // 记录当前联系人的手机号
54.         }
55.     }
57.     // 开始合并
58.     map<int, vector<int>> unio; // 父节点和其子集
59.     map<string, vector<vector<string>>> res; // 一个名字可能对应多个通讯录号
60.     for (int i = 0; i < n; i++) {
61.         int cf = find(i); // 找到当前联系人的根节点
62.         unio[cf].push_back(i); // 合并到同一个集合
63.     }
65.     // 排序并输出结果
66.     for (auto& f : unio) {
67.         string cur_name;
68.         set<string> cur_phone; // 去重并排序手机号
69.         for (int c : f.second) {
70.             // 查询当前集合的名字最小值
71.             if (cur_name.size() == 0)
72.                 cur_name = name[c];
73.             else
74.                 cur_name = min(cur_name, name[c]);
75.             // 合并当前联系人的所有手机号
76.             for (int i = 0; i < phone[c].size(); i++) {
77.                 cur_phone.insert(phone[c][i]);
78.             }
79.         }
80.         vector<string> v_phone(cur_phone.begin(), cur_phone.end());
81.         res[cur_name].push_back(v_phone); // 保存结果
82.     }
84.     // 按姓名和手机号的ASCII码升序排序
85.     for (auto& t : res) {
86.         sort(t.second.begin(), t.second.end());
87.         for (auto c : t.second) {
88.             cout << t.first;
89.             for (int i = 0; i < c.size(); i++)
90.                 cout << " " << c[i];
91.             cout << "\n";
92.         }
93.     }
94.     return 0;
95. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。