整合邮箱的C++实现

newbee_wxh

于 2022-03-22 16:48:12 发布

阅读量4.9k

点赞数

分类专栏：面试总结文章标签：哈希算法

本文链接：https://blog.csdn.net/csdnwxhw/article/details/123665055

版权

面试总结专栏收录该内容

7 篇文章

订阅专栏

该博客展示了如何使用C++实现一个邮箱账户合并的算法。通过UnionFind数据结构，将具有相同所有者的邮箱地址进行整合，最终返回每个所有者的所有邮箱地址列表。示例代码中，给出了一个包含多个邮箱账户的列表，并演示了如何调用这个合并函数进行处理。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

整合邮箱的C++实现

#include <map>
#include <unordered_map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class UnionFind{
private:
    unordered_map<string, string> father;
    unordered_map<string, vector<string>> accounts;

public:
    unordered_map<string, string> get_father(){
        return father;
    }
    unordered_map<string, vector<string>> get_accounts(){
        return accounts;
    }
    string find(string s){
        if(father[s] == "root") return s;
        father[s] = find(father[s]);
        return father[s];
    }
    void merge(string x, string y){
        string root_x = find(x);
        string root_y = find(y);
        if(root_x == root_y) return;
        if(accounts[root_x].size() < accounts[root_y].size()){
            father[root_x] = root_y;
            for(auto &account : accounts[root_x])
                accounts[root_y].push_back(account);
            accounts.erase(root_x);
        }else{
            father[root_y] = root_x;
            for(auto &account : accounts[root_y])
                accounts[root_x].push_back(account);
            accounts.erase(root_y);
        }
    }
    void add(string x){
        if(!father.count(x)){
            father[x] = "root";
            accounts[x] = {x};
        }
    }

};

class Solution{
public:
    static vector<vector<string>> accountsMerge(vector<vector<string>> &accounts){
        UnionFind uf;
        unordered_map<string, string> email_to_name;
        for(auto& v : accounts){
            string name = v[0];
            string master = v[1];
            email_to_name[master] = name;
            uf.add(master);
            
            for(int i = 2; i < v.size(); i++){
                email_to_name[v[i]] = name;
                uf.add(v[i]);
                uf.merge(master,v[i]);
            }
        }
        vector<vector<string>> res;
        unordered_map<string, string> father = uf.get_father();
        unordered_map<string, vector<string>> acc = uf.get_accounts();
        for(auto &p : father){
            if(p.second == "root"){
                vector<string> user_account = {email_to_name[p.first]};
                sort(acc[p.first].begin(), acc[p.first].end());
                for(auto &email : acc[p.first])
                    user_account.push_back(email);
                res.push_back(user_account);
            }
        }
        return res;
    }
};

int main()
{
    vector<vector<string>> ats(4);
    ats[0][0] = "John";
    ats[0][1] = "johnsmith@mail.com";
    ats[0][2] = "john00@mail.com";
    ats[1][0] = "John";
    ats[1][1] = "johnnybravo@mail.com";
    ats[2][0] = "John";
    ats[2][1] = "johnsmith@mail.com";
    ats[2][2] = "john_newyork@mail.com";
    ats[3][0] = "Mary";
    ats[3][1] = "mary@mail.com";
    Solution::accountsMerge(ats);
    return 0;
}