题面解释:

你有一个通讯录，其中每个联系人包含姓名和多个手机号。如果两个联系人拥有相同的手机号，认为他们是同一个人，需要将其合并。如果合并时发现姓名不同，则保留字典序较小的姓名。通讯录中记录的手机号最多有10个，且每个手机号由1到10位数字组成。输入第一行为记录数量，接下来每行为一条联系人记录，包含姓名和若干手机号，手机号之间用空格隔开。输出时，整理后的通讯录需要按姓名字典序排列，同一联系人的手机号也按升序排列。

思路:并查集 + 哈希 + 自定义排序

1.基于共享电话号码的联系人属于同一组的思路，我们可以先使用哈希表将电话号码映射到对应的联系人编号列表上，然后使用并查集将共享同一电话号码的联系人合并到同一组。

2.对于并查集里的每个组（用该集合中的root节点编号表示），我们需要找到字典序最小的联系人姓名和该组内的联系人的所有电话号码。

我们可以使用一个哈希表来存储每个组（用该集合中的root节点编号表示）的最小字典序的姓名和所有电话号码。

3.最后，我们将每个组的姓名及电话号码（按字典序排序）存储到结果列表中，并对结果列表进行一个字典序排序。

代码步骤

1. 并查集的使用：

   • 每个联系人初始时自己是一个独立的集合，我们将通过电话号码来判断哪些联系人属于同一个集合。如果两个联系人有相同的电话号码，则他们应该属于同一个集合，使用并查集进行合并。

2. 电话号码映射到联系人：

   • 我们使用一个哈希表，存储电话号码与联系人编号的映射。如果发现某个号码已经属于某个联系人编号，则合并当前联系人和对应联系人。

3. 合并后的联系人处理：

   • 在并查集中的每个集合里，找到字典序最小的姓名，并且合并所有电话号码。
   • 电话号码合并后需要进行去重，并按字典序排序。

4. 输出排序：

   • 对最终的合并结果按姓名和电话号码进行排序，并输出。

复杂度分析：

• 时间复杂度：主要是并查集的合并和查找操作，其均摊时间复杂度为 O(α(n))，几乎接近常数。此外，还需对所有联系人进行排序，总复杂度为 O(n log n)。

• 空间复杂度：O(n) 用于存储联系人信息和并查集的辅助数组。

代码

python

# 输入联系人数量
num = int(input())

# 输入联系人姓名及其电话号码，并按行存储
arr = [input().split() for _ in range(num)]

# 创建一个字典，用于映射电话号码到对应的联系人编号列表
phone_to_id = {}

# 遍历每个联系人，将他们的电话号码加入映射字典中
for i in range(num):
    for phone in arr[i][1:]:
        if phone in phone_to_id:
            # 如果电话号码已经存在，添加当前联系人编号到列表中
            phone_to_id[phone].append(i)
        else:
            # 如果电话号码不存在，初始化一个列表并存储联系人编号
            phone_to_id[phone] = [i]

# 初始化并查集，每个联系人最初是自己所在组的代表
fa = [i for i in range(num)]

# 查找函数（带路径压缩），查找当前联系人所在组的根节点
def find(x):
    if x != fa[x]:
        fa[x] = find(fa[x])  # 路径压缩
    return fa[x]

# 合并两个组，将两个联系人的组合并到一起
def merge(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        fa[x] = y  # 合并操作

# 判断两个联系人是否属于同一组
def same(x, y):
    return find(x) == find(y)

# 遍历每个电话号码，将共享同一电话号码的联系人合并到同一组
for phone in phone_to_id:
    first_id = phone_to_id[phone][0]  # 获取第一个联系人的编号
    for i in range(1, len(phone_to_id[phone])):
        merge(first_id, phone_to_id[phone][i])  # 合并其他拥有相同电话号码的联系人

# 创建字典，用于存储每个组的最小字典序的姓名和所有电话号码
root_to_name = {}
root_to_phones = {}

# 遍历每个联系人，按组进行合并处理
for i in range(num):
    root = find(i)  # 查找联系人的根节点（代表组）

    # 如果该组已经有一个名字，则比较字典序
    if root in root_to_name:
        # 更新为字典序更小的姓名
        if arr[i][0] <= root_to_name[root]:
            root_to_name[root] = arr[i][0]
    else:
        # 如果该组还没有姓名，则赋值当前联系人的姓名
        root_to_name[root] = arr[i][0]

    # 合并该联系人的所有电话号码到所在组
    for phone in arr[i][1:]:
        if root in root_to_phones:
            # 如果该组已经有电话号码，则继续添加
            root_to_phones[root].add(phone)
        else:
            # 如果该组没有电话号码，则初始化一个集合并添加
            root_to_phones[root] = {phone}

# 结果存储列表
res = []

# 构建结果列表，包含每个组的姓名及电话号码（按字典序排序）
for root in root_to_name:
    res.append([root_to_name[root]] + sorted(list(root_to_phones[root])))

# 对结果列表进行排序
res.sort()

# 输出合并后的联系人姓名及电话号码
for x in res:
    print(' '.join(x))

java

import java.util.*;

public class Main {
    static int[] parent;

    public static int find(int x){
        if(parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public static void union(int x, int y){
        parent[find(x)] = find(y);
    }

    static class Contact{
        String name;//联系人姓名
        Set<String> phoneNum;//联系人电话
        int id;

        Contact(String name,Set<String> phoneNum,int id){
            this.name = name;
            this.phoneNum = phoneNum;
            this.id = id;
        }
    }
    //合并后
    static class MergedContact{
        String name;
        Set<String> phoneNum;

        MergedContact(String name,Set<String> phoneNum){
            this.name = name;
            this.phoneNum = phoneNum;
        }

        String getMinPhoneNumber(){
            return Collections.min(phoneNum);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //记录数量
        int recordCount = sc.nextInt();
        sc.nextLine();
        //联系人列表
        List<Contact> contacts = new ArrayList<>();
        parent = new int[recordCount];

        //初始化并查集
        for(int i=0;i<recordCount;i++){
            parent[i] = i;
        }

        Map<String,Integer> phoneToContactId = new HashMap<>();

        for (int i = 0; i < recordCount; i++) {
            String input = sc.nextLine().trim();
            String[] tokens = input.trim().split("\\s+");
            String name = tokens[0];

            Set<String> phoneNumber = new HashSet<>();
            for (int j = 1; j < tokens.length; j++) {
                String phone = tokens[j];
                phoneNumber.add(phone);
                if (!phoneToContactId.containsKey(phone)) {
                    phoneToContactId.put(phone, i);
                } else {
                    int otherId = phoneToContactId.get(phone);
                    union(i, otherId);
                }
            }
            contacts.add(new Contact(name, phoneNumber, i));
        }
        //合并联系人
        Map<Integer,MergedContact> rootIdToMergedContact = new HashMap<>();
        for(int i=0;i<recordCount;i++){
            int root  = find(i);
            Contact contact = contacts.get(i);
            if(!rootIdToMergedContact.containsKey(root)){
                rootIdToMergedContact.put(root,new MergedContact(contact.name,new HashSet<>(contact.phoneNum)));
            }else{
                MergedContact mergedContact = rootIdToMergedContact.get(root);
                //更新姓名
                if(contact.name.compareTo(mergedContact.name) < 0){
                    mergedContact.name = contact.name;
                }
                mergedContact.phoneNum.addAll(contact.phoneNum);
            }
        }

        List<MergedContact> mergedContacts = new ArrayList<>(rootIdToMergedContact.values());
        for(MergedContact mc : mergedContacts){
            //将电话号码集改为TreeSet进行排序
            mc.phoneNum = new TreeSet<>(mc.phoneNum);
        }

        mergedContacts.sort((a,b)->{
            int nameCompare = a.name.compareTo(b.name);
            if(nameCompare!=0){
                return nameCompare;
            }else {
                String minPhoneA = a.getMinPhoneNumber();
                String minPhoneB = b.getMinPhoneNumber();
                return minPhoneA.compareTo(minPhoneB);
            }
        });

        for(MergedContact mc:mergedContacts){
           StringBuilder sb = new StringBuilder();
           sb.append(mc.name);

            List<String> sortedphones = new ArrayList<>(mc.phoneNum);
            Collections.sort(sortedphones);
            for(String phone : sortedphones){
                sb.append(" ").append(phone);
            }
            System.out.println(sb.toString());
        }
        sc.close();
    }

}

cpp

#include <bits/stdc++.h>
using namespace std;

int parent[1005];  // 并查集数组，用于存储每个联系人的父节点
int visited[1005]; // 记录某个联系人组是否已经处理过
struct Contact {
    int id;              // 联系人编号
    string name;         // 联系人姓名
    set<string> phones;  // 电话号码集合
} contacts[1005], mergedContacts[1005];
int mergedCount = 0;    // 合并后的联系人数量

// 并查集的查找操作，查找 x 的根节点
int findParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = findParent(parent[x]);  // 路径压缩优化
}

// 并查集的合并操作，将 x 和 y 所在的组合并
void unionGroups(int x, int y) {
    int rootX = findParent(x);
    int rootY = findParent(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;  // 将 x 所在的组的根节点指向 y 所在组的根节点
    }
}

// 比较函数，用于对联系人进行排序
bool compareContacts(Contact a, Contact b) {
    if (a.name != b.name) return a.name < b.name;
    string minPhoneA = *(a.phones.begin());
    string minPhoneB = *(b.phones.begin());
    return minPhoneA < minPhoneB;
}

int main() {
    int n;  // 联系人数
    cin >> n;

    // 初始化并查集，每个联系人初始时自己是自己的父节点
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    string inputLine;
    getline(cin, inputLine);  // 吃掉换行符
    for (int i = 1; i <= n; i++) {
        getline(cin, inputLine);
        int length = inputLine.length();

        Contact contact = {};  // 新建一个联系人
        int wordCount = 0;
        string word = "";

        // 解析输入，将姓名和电话号码分割存储
        for (int j = 0; j < length; j++) {
            word += inputLine[j];
            if (j == length - 1 || inputLine[j + 1] == ' ') {
                if (wordCount == 0) {
                    contact.name = word;  // 第一个单词为姓名
                } else {
                    contact.phones.insert(word);  // 后续的为电话号码
                }
                wordCount++;
                word = "";
                j++;  // 跳过空格
            }
        }

        contacts[i] = contact;  // 存储联系人信息

        // 合并当前联系人与前面所有联系人，检查是否有相同的电话号码
        for (int j = 1; j < i; j++) {
            for (const string &phoneJ : contacts[j].phones) {
                for (const string &phoneI : contact.phones) {
                    if (phoneJ == phoneI) {
                        unionGroups(j, i);  // 如果有相同号码则合并
                    }
                }
            }
        }
    }

    // 将联系人进行合并
    for (int i = 1; i <= n; i++) {
        int root = findParent(i);  // 找到联系人所在的组
        if (visited[root] == 0) {
            mergedContacts[++mergedCount] = contacts[i];  // 新组加入联系人
            visited[root] = mergedCount;  // 标记该组已处理
        } else {
            // 如果该组已存在联系人，则合并信息
            if (contacts[i].name < mergedContacts[visited[root]].name) {
                mergedContacts[visited[root]].name = contacts[i].name;  // 更新为字典序较小的姓名
            }
            // 合并电话号码
            for (const string &phone : contacts[i].phones) {
                mergedContacts[visited[root]].phones.insert(phone);
            }
        }
    }

    // 按规则排序联系人
    sort(mergedContacts + 1, mergedContacts + mergedCount + 1, compareContacts);

    // 输出结果
    for (int i = 1; i <= mergedCount; i++) {
        cout << mergedContacts[i].name << ' ';
        for (const string &phone : mergedContacts[i].phones) {
            cout << phone << ' ';
        }
        cout << '\n';
    }

    return 0;
}

本题为2024年10月12日-华为国内机考原题

华为机考的介绍点击这里

题目内容

你有一个通讯录，这个通讯录里每个联系人都包含姓名和手机号，一个联系人可能有多个手机号。

如果发现两个联系人拥有相同的手机号，我们就认为他们是同一个人。

你的任务就是整理这个通讯录，将具有相同手机号的联系人合并为一个联系人，并返回合并后的通讯录列表。

注意：用例不保证具有相同手机号的联系人姓名肯定是相同的，如果合并的时候发现联系人姓名不同，那么以字典序小的为姓名。

输入描述

第一行表示通讯录的记录数量$num$，值的范围[$1, 1000$]。

从第二行开始，每一行代表一条联系人记录，每条录包括姓名和若干电话号码，电话号码的个数不超过$10$（姓名由英文字母大小写组成，长度在1到10之间，电话号码由数字组成）。

之后的若干条记录代表人的记录（手机号个数$1$到$10$位数字不重复）。同一条记录里的电话号码用空格隔开，电话号码的长度在[$1,10$]

输出描述

整理后的通讯录列表，其中如果两个联系人被识别为同一个人，则他们的电话号码合并。

输出联系人姓名和手机号码列表按$ASCII$码升序排序。

样例1

输入

4 
kaka 10000000000 10000000001 
tata 10000000020 
kaka 10000000000 10000000002 
tata 10000000010

输出

kaka 10000000000 10000000001 10000000002 
tata 10000000010 
tata 10000000020 

说明

在这个通讯录中，第一个kaka和第二个kaka有相同的手机号“10000000000”，因此他们被视为同一个人。

因此kaka一共有三个号码并按ASCII码升级排序结果是10000000000 10000000001 10000000002。

第一个tata和第二个tata没有相同的号码，因此被视作两个人。

样例2

输入

3
kaka 10000000000 10000000001
kaka 10000000001 10000000002
kaka 10000000002 10000000003

输出

kaka 10000000000 10000000001 10000000002 10000000003

说明

在这个通讯录中，第一个kaka和第二个kaka有相同的手机号“10000000001”，第二个kaka和第三个kaka有相同的手机号“10000000002”，因此题目被视为同一个人。

因此kaka一共有四个号码并按ASCII码升级排序结果是10000000000 10000000001 10000000002 10000000003