Accounts Merge

分类：LeetCode 发布于：2019-10-20 ID：721

难度：中等
通过率： 37.9%
题目链接：https://leetcode-cn.com/problems/accounts-merge

题目描述

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

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

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

例子 1:

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]的范围内。

解法：

template <typename T>
class Hash_UF{
public:
    explicit Hash_UF(){
        union_count = 0;
    }

    int count(){
        return union_count;
    }

    bool connected(const T& p, const T& q){
        return find(p) == find(q);
    }

    void connect(const T& p, const T& q){
        insert_if_not_exist(p);
        insert_if_not_exist(q);

        int pid = find(p);
        int qid = find(q);
        if(pid == qid) return;
        if(sz[pid] > sz[qid]){
            id[qid] = pid;
            sz[pid] += sz[qid];
        }else{
            id[pid] = qid;
            sz[qid] += sz[pid];
        }
        union_count--;
    }

    void insert_if_not_exist(const T &p){
        if(id.find(p) == id.end()){
            id[p] = p;
            union_count++;
        }
    }

    T find(T p){
        while(id[p] != p){
            id[p] = id[id[p]];
            p = id[p];
        }
        return p;
    }
private:
    unordered_map<T, T> id;
    int union_count;
    unordered_map<T, size_t> sz;
};


class Vocab{
public:
    using iterator = typename unordered_map<string, int>::iterator;

    size_t token_to_id(const string &token){
        auto it = vocab.find(token);
        if(it == vocab.end()){
            num_vocab += 1;
            vocab[token] = num_vocab;
            return num_vocab;
        }else{
            return it->second;
        }
    }

    iterator begin(){
        return vocab.begin();
    }
    iterator end(){
        return vocab.end();
    }

private:
    unordered_map<string, int> vocab;
    size_t num_vocab = 0;
};


class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        Hash_UF<int> uf;
        Vocab vocab;

        unordered_map<string, int> name_to_group;
        unordered_map<int, vector<string>> group_to_account;

        for(auto &account: accounts){
            auto it = account.begin();
            ++it; // skip name

            int id1 = vocab.token_to_id(*it);
            uf.insert_if_not_exist(id1); // insert first account
            ++it;
            for(;it != account.end();++it){
                int id2 = vocab.token_to_id(*it);
                uf.connect(id1, id2);
                id1 = id2;
            }
        }

        // add name to group
        for(auto &account: accounts){
            auto it = account.begin();
            string &name = *it;
            ++it;
            int id1 = vocab.token_to_id(*it);
            int group_id = uf.find(id1);
            if(group_to_account[group_id].empty()){
                group_to_account[group_id].push_back(name);
            }
        }

        // add account to certain group
        for(auto it=vocab.begin();it!=vocab.end();++it){
            int group_id = uf.find(it->second);
            group_to_account[group_id].push_back(it->first);
        }

        // sort every group
        vector<vector<string>> ret;
        for(auto it=group_to_account.begin();it!=group_to_account.end();++it){
            sort(it->second.begin()+1, it->second.end());
            ret.push_back(::move(it->second));
        }
        return ret;
    }
};

LeetCode 题解

积跬步，至千里。

Accounts Merge

题目描述

解法：