账户合并

发表于
本文字数： 3k 阅读时长 ≈ 3 分钟

LeetCode每日一题，721. Accounts Merge

先看题目描述

syxppd.png

大意就是给定的列表包含账户的用户名和邮箱，让我们将属于同一个人的账户合并，并将合并后的账户返回，要求按照给定的格式返回账户

算法和思路

并查集 + 哈希表

两个账户需要合并，当且仅当两个账户至少有一个共同的邮箱地址，因此这道题的实质是判断所有的邮箱地址中有哪些邮箱地址必定属于同一人，可以使用并查集实现

我们需要三个哈希表 names，nodes 和 emails，nodes 是为邮箱地址编号，将邮箱地址映射到某个唯一的编号，names 是将邮箱编号映射到账户的用户名，emalis 是将根邮箱编号映射到该邮箱所属人拥有的所有邮箱地址，names 和 emails 是用与构造最后的答案的

首先遍历每个账户，为每个邮箱地址进行编号；然后再次遍历每个账户，由于同一个账户中的邮箱地址一定属于同一个人，于是用并查集将同一个邮箱地址均合并

完成并查集的合并操作后，即可知道合并后有多少个不同的账户，再遍历每个邮箱地址，获取该邮箱对应的根邮箱的编号，将该邮箱地址存储到对应的优先级队列中，最后构造结果并返回即可

算法源码

并查集 + 哈希表

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    private int[] parent;

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int num = 0;
        Map<Integer, String> names = new HashMap<>();
        Map<String, Integer> nodes = new HashMap<>();
        Map<Integer, PriorityQueue<String>> emails = new HashMap<>();
        List<List<String>> res = new ArrayList<>();
        for (List<String> account : accounts) {
             for (int i = 1; i < account.size(); i++) {
                 if (!nodes.containsKey(account.get(i))) {
                     names.put(num, account.get(0));
                     nodes.put(account.get(i), num++);
                 }
             }
        }
        this.parent = new int[num];
        for (int i = 0; i < num; i++) {
            this.parent[i] = i;
        }
        for (List<String> account : accounts) {
            if (account.size() < 3) {
                continue;
            }
            int root = nodes.get(account.get(1));
            for (int i = 2; i < account.size(); i++) {
                union(root, nodes.get(account.get(i)));
            }
        }
        for (Map.Entry<String, Integer> entry : nodes.entrySet()) {
            int root = find(entry.getValue());
            if (!emails.containsKey(root)) {
                PriorityQueue<String> prior = new PriorityQueue<>();
                prior.offer(entry.getKey());
                emails.put(root, prior);
            } else {
                emails.get(root).offer(entry.getKey());
            }
        }
        for (Map.Entry<Integer, PriorityQueue<String>> entry : emails.entrySet()) {
            List<String> cur = new ArrayList<>();
            cur.add(names.get(entry.getKey()));
            PriorityQueue<String> prior = entry.getValue();
            while (!prior.isEmpty()) {
                cur.add(prior.poll());
            }
            res.add(cur);
        }
        return res;
    }

    private int find(int x) {
        if (x != this.parent[x]) {
            this.parent[x] = find(this.parent[x]);
        }
        return this.parent[x];
    }

    private void union(int a, int b) {
        int x = find(a);
        int y = find(b);
        this.parent[y] = x;
    }
}