题目描述

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。

现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。

合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。

样例

Input: 
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation: 
  第一个和第三个 John 是同一个人，因为他们有共同的电子邮件 "johnsmith@mail.com"。 
  第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址没有被其他帐户使用。
  我们可以以任何顺序返回这些列表，例如答案[['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
  ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']]仍然会被接受。

注意：

accounts的长度将在[1，1000]的范围内。
accounts[i]的长度将在[1，10]的范围内。
accounts[i][j]的长度将在[1，30]的范围内。

算法

(并查集)

思路图:

有思路图就不展开细讲，主要是并查集合一定要会默写。

时间复杂度 O(nlogn)

Java 代码

class Solution {

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int size = accounts.size();
        List<List<String>> res = new ArrayList<>(size);
        if (size == 0) {
            return res;
        }
        UF uf = new UF(size);

        Map<String, Integer> emailToPersonId = new HashMap<>();
        for (int i = 0; i < size; i++) {
            List<String> account = accounts.get(i);
            for (int j = 1; j < account.size(); j++) {
                String email = account.get(j);
                if (emailToPersonId.containsKey(email)) {
                    Integer prePersonId = emailToPersonId.get(email);
                    uf.union(prePersonId, i);
                }
                emailToPersonId.put(email, i);
            }
        }

        Map<Integer, Set<String>> rootPersonIdToEmails = new HashMap<>();
        for (int i = 0; i < size; i++) {
            int rootPersonId = uf.find(i);
            List<String> emails = accounts.get(i).subList(1, accounts.get(i).size());
            if (rootPersonIdToEmails.containsKey(rootPersonId)) {
                rootPersonIdToEmails.get(rootPersonId).addAll(emails);
            } else {
                rootPersonIdToEmails.put(rootPersonId, new TreeSet<>(emails));
            }
        }

        for (Map.Entry<Integer, Set<String>> entry : rootPersonIdToEmails.entrySet()) {
            List<String> sub = new ArrayList<>();
            int rootPersonId = entry.getKey();
            String name = accounts.get(rootPersonId).get(0);
            sub.add(name);
            sub.addAll(entry.getValue());
            res.add(sub);
        }

        return res;
    }
}

class UF {
    int[] parent;
    int[] rank;     // 表示i为root的集合所表示的高度

    public UF(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int getSize() {
        return parent.length;
    }

    // 查找元素p对应的集合编号, O(h)复杂度
    public int find(int p) {
        if (p < 0 || p >= getSize()) {
            throw new IllegalArgumentException("p is out of bound");
        }

        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }

        return p;
    }

    // 元素p和元素q所在两个集合合并,O(h)复杂度
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }

        // 根据集合高度来判断合并方向
        // rank低的合并到rank高的
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        } else if (rank[pRoot] > rank[qRoot]) {
            parent[qRoot] = pRoot;
        } else {
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;
        }
    }

    // 查看元素p和元素q是否在一个集合
    // O(h)复杂度
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

}