rust 解法, 执行用时: 28 ms, 内存消耗: 4.6 MB, 提交时间: 2024-07-15 07:46:34

impl Solution {
    pub fn accounts_merge(accounts: Vec<Vec<String>>) -> Vec<Vec<String>> {
        // dfs
        let mut graph = std::collections::HashMap::new();
        let mut mail2account = std::collections::HashMap::new();
        for i in 0..accounts.len() {
            let name = &accounts[i][0];
            for j in 1..accounts[i].len() {
                mail2account.entry(&accounts[i][j]).or_insert(name);
            }

            for j in 2..accounts[i].len() {
                graph.entry(&accounts[i][j - 1]).or_insert(Vec::new()).push(&accounts[i][j]);
                graph.entry(&accounts[i][j]).or_insert(Vec::new()).push(&accounts[i][j - 1]);
            }
        }

        let mut visited = std::collections::HashSet::new();
        let mut answer = Vec::new();
        for i in 0..accounts.len() {
            if accounts[i].len() > 0 && !visited.contains(&accounts[i][1]) {
                let mut stack = vec![&accounts[i][1]];
                let mut emails = Vec::new();
                while !stack.is_empty() {
                    let email = stack.pop().unwrap();
                    if visited.insert(email) {
                        emails.push(email.to_string());
                        if let Some(nexts) = graph.get(email) {
                            for next in nexts.iter() {
                                stack.push(next);
                            }
                        }
                    }
                }
                emails.sort_unstable();
                let mut row = vec![mail2account.get(&accounts[i][1]).unwrap().to_string()];
                row.append(&mut emails);
                answer.push(row);
            }
        }
        answer
    }
}

rust 解法, 执行用时: 87 ms, 内存消耗: 3.9 MB, 提交时间: 2024-07-15 07:46:13

impl Solution {
    pub fn accounts_merge(accounts: Vec<Vec<String>>) -> Vec<Vec<String>> {
        // union-find
        let mut parents = std::collections::HashMap::new();
        let mut mail2account = std::collections::HashMap::new();
        for i in 0..accounts.len() {
            let name = &accounts[i][0];
            for j in 1..accounts[i].len() {
                parents.entry(&accounts[i][j]).or_insert(&accounts[i][j]);
                mail2account.entry(&accounts[i][j]).or_insert(name);
            }
        }

        for i in 0..accounts.len() {
            for j in 2..accounts[i].len() {
                let mut a = &accounts[i][j - 1];
                let mut b = &accounts[i][j];
                while &a != parents.get(a).unwrap() { a = parents.get(a).unwrap(); }
                while &b != parents.get(b).unwrap() { b = parents.get(b).unwrap(); }
                if a == b { continue; }
                *parents.get_mut(b).unwrap() = a;
            }
        }

        let mut sets = std::collections::HashMap::new();
        for (&k, &v) in parents.iter() {
            let mut root = k;
            while &root != parents.get(root).unwrap() { root = parents.get(root).unwrap(); }
            sets.entry(root).or_insert(Vec::new()).push(k);
        }

        let mut answer = Vec::new();
        sets.into_iter().for_each(|(head, set)| {
            let mut row = vec![mail2account.get(head).unwrap().to_string()];
            let mut mails: Vec<String> = set.into_iter().map(|s| s.to_string()).collect();
            mails.sort_unstable();
            row.append(&mut mails);
            answer.push(row);
        });
        answer
    }
}

golang 解法, 执行用时: 48 ms, 内存消耗: 7.8 MB, 提交时间: 2023-09-23 00:19:59

func accountsMerge(accounts [][]string) (ans [][]string) {
    emailToIndex := map[string]int{}
    emailToName := map[string]string{}
    for _, account := range accounts {
        name := account[0]
        for _, email := range account[1:] {
            if _, has := emailToIndex[email]; !has {
                emailToIndex[email] = len(emailToIndex)
                emailToName[email] = name
            }
        }
    }

    parent := make([]int, len(emailToIndex))
    for i := range parent {
        parent[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    union := func(from, to int) {
        parent[find(from)] = find(to)
    }

    for _, account := range accounts {
        firstIndex := emailToIndex[account[1]]
        for _, email := range account[2:] {
            union(emailToIndex[email], firstIndex)
        }
    }

    indexToEmails := map[int][]string{}
    for email, index := range emailToIndex {
        index = find(index)
        indexToEmails[index] = append(indexToEmails[index], email)
    }

    for _, emails := range indexToEmails {
        sort.Strings(emails)
        account := append([]string{emailToName[emails[0]]}, emails...)
        ans = append(ans, account)
    }
    return
}

javascript 解法, 执行用时: 124 ms, 内存消耗: 52.2 MB, 提交时间: 2023-09-23 00:19:40

/**
 * @param {string[][]} accounts
 * @return {string[][]}
 */
var accountsMerge = function(accounts) {
    const emailToIndex = new Map();
    const emailToName = new Map();
    let emailsCount = 0;
    for (const account of accounts) {
        const name = account[0];
        const size = account.length;
        for (let i = 1; i < size; i++) {
            const email = account[i];
            if (!emailToIndex.has(email)) {
                emailToIndex.set(email, emailsCount++);
                emailToName.set(email, name);
            }
        }
    }

    const uf = new UnionFind(emailsCount);
    for (const account of accounts) {
        const firstEmail = account[1];
        const firstIndex = emailToIndex.get(firstEmail);
        const size = account.length;
        for (let i = 2; i < size; i++) {
            const nextEmail = account[i];
            const nextIndex = emailToIndex.get(nextEmail);
            uf.union(firstIndex, nextIndex);
        }
    }

    const indexToEmails = new Map();
    for (const email of emailToIndex.keys()) {
        const index = uf.find(emailToIndex.get(email));
        const account = indexToEmails.get(index) ? indexToEmails.get(index) : [];
        account.push(email);
        indexToEmails.set(index, account);
    }
    const merged = [];
    for (const emails of indexToEmails.values()) {
        emails.sort();
        const name = emailToName.get(emails[0]);
        const account = [];
        account.push(name);
        account.push(...emails);
        merged.push(account);
    }
    return merged;
};

class UnionFind {
    constructor (n) {
        this.parent = new Array(n).fill(0).map((element, index) => index);
    }

    union (index1, index2) {
        this.parent[this.find(index2)] = this.find(index1);
    }

    find (index) {
        if (this.parent[index] !== index) {
            this.parent[index] = this.find(this.parent[index]);
        }
        return this.parent[index];
    }
}

java 解法, 执行用时: 31 ms, 内存消耗: 46.4 MB, 提交时间: 2023-09-23 00:19:23

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Integer> emailToIndex = new HashMap<String, Integer>();
        Map<String, String> emailToName = new HashMap<String, String>();
        int emailsCount = 0;
        for (List<String> account : accounts) {
            String name = account.get(0);
            int size = account.size();
            for (int i = 1; i < size; i++) {
                String email = account.get(i);
                if (!emailToIndex.containsKey(email)) {
                    emailToIndex.put(email, emailsCount++);
                    emailToName.put(email, name);
                }
            }
        }
        UnionFind uf = new UnionFind(emailsCount);
        for (List<String> account : accounts) {
            String firstEmail = account.get(1);
            int firstIndex = emailToIndex.get(firstEmail);
            int size = account.size();
            for (int i = 2; i < size; i++) {
                String nextEmail = account.get(i);
                int nextIndex = emailToIndex.get(nextEmail);
                uf.union(firstIndex, nextIndex);
            }
        }
        Map<Integer, List<String>> indexToEmails = new HashMap<Integer, List<String>>();
        for (String email : emailToIndex.keySet()) {
            int index = uf.find(emailToIndex.get(email));
            List<String> account = indexToEmails.getOrDefault(index, new ArrayList<String>());
            account.add(email);
            indexToEmails.put(index, account);
        }
        List<List<String>> merged = new ArrayList<List<String>>();
        for (List<String> emails : indexToEmails.values()) {
            Collections.sort(emails);
            String name = emailToName.get(emails.get(0));
            List<String> account = new ArrayList<String>();
            account.add(name);
            account.addAll(emails);
            merged.add(account);
        }
        return merged;
    }
}

class UnionFind {
    int[] parent;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public void union(int index1, int index2) {
        parent[find(index2)] = find(index1);
    }

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

cpp 解法, 执行用时: 160 ms, 内存消耗: 54.9 MB, 提交时间: 2023-09-23 00:18:44

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:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        UnionFind uf;
        // email -> name
        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"){
                // 添加user
                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;

    }
};

cpp 解法, 执行用时: 120 ms, 内存消耗: 50.5 MB, 提交时间: 2023-09-23 00:17:44

class Solution {
public:
    unordered_map<string,vector<string>> build_graph(vector<vector<string>>& accounts){
        /* 建图 */
        unordered_map<string,vector<string>> graph;
        
        for(auto& account: accounts){
            
            string master = account[1];
            
            // 对剩余账户做一个去重
            for(auto& email: unordered_set<string>(account.begin()+2,account.end())){
                
                graph[master].push_back(email);
                graph[email].push_back(master);
            }
        }
        
        return graph;
    }
    
    void dfs(unordered_map<string,vector<string>>& graph,unordered_set<string>& visited,string& email,vector<string>& emails){
        /* 深搜遍历 */
        // 已经访问过的就剪枝
        if(visited.count(email))
            return;
        
        visited.insert(email);
        emails.push_back(email);
        
        // 对邻居节点继续深搜
        for(auto& neighbor: graph[email])
            dfs(graph,visited,neighbor,emails);
    }
    
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        // 建图
        unordered_map<string,vector<string>> graph = build_graph(accounts);
        
        vector<vector<string>> res;
        
        unordered_set<string> visited;
        
        for(auto& account: accounts){
            vector<string> emails;
            // 深搜得到name的所有邮箱
            dfs(graph,visited,account[1],emails);
            
            if(emails.empty())
                continue;
            
            // 排序，添加姓名，加入到答案中
            sort(emails.begin(),emails.end());
            emails.insert(emails.begin(),account[0]);
            res.push_back(emails);
        }
        
        return res;
    }
};

python3 解法, 执行用时: 84 ms, 内存消耗: 20.6 MB, 提交时间: 2023-09-23 00:17:29

class Solution:
    def build_graph(self,accounts):
        """
        建图
        """
        graph = collections.defaultdict(list)
        for account in accounts:
            master = account[1]
            # 对剩余账户做一个去重
            for email in list(set(account[2:])):
                graph[master].append(email)
                graph[email].append(master)
        
        return graph
    
    def dfs(self,email,graph,visited,emails):
        """
        深搜遍历
        """
        # 已经访问过的就剪枝
        if email in visited:
            return 
        
        visited.add(email)
        emails.append(email)
        
        # 对邻居节点继续深搜
        for neighbor in graph[email]:
            self.dfs(neighbor,graph,visited,emails)
    
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        graph = self.build_graph(accounts)

        res = []
        visited = set()
        for account in accounts:
            emails = []
            self.dfs(account[1],graph,visited,emails)
            if emails:
                res.append([account[0]] + sorted(emails))
        
        return res

python3 解法, 执行用时: 112 ms, 内存消耗: 19.5 MB, 提交时间: 2023-09-23 00:17:19

class UnionFind:
    def __init__(self):
        self.father = {}
        # 根节点所在集合的所有账户
        self.accounts = {}
        
    def find(self,x):
        if not self.father[x]: return x
        
        # 递归的路径压缩处理
        self.father[x] = self.find(self.father[x])
        
        return self.father[x]
    
    def merge(self,x,y):
        root_x,root_y = self.find(x),self.find(y)
        
        if root_x == root_y:
            return
        
        # 按秩合并，更新根节点和所属的账户
        if len(self.accounts[root_x]) > len(self.accounts[root_y]):
            self.father[root_y] = root_x
            self.accounts[root_x] += self.accounts[root_y]
            del self.accounts[root_y]
        else:
            self.father[root_x] = root_y
            self.accounts[root_y] += self.accounts[root_x]
            del self.accounts[root_x]
    
    def add(self,x):
        if x not in self.father:
            self.father[x] = None
            self.accounts[x] = [x]

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        uf = UnionFind()
        for account in accounts:
            # 找到姓名和主账户
            name,master = account[0],account[1]
            uf.add((name,master))
            
            # 和其余的账户一一合并
            account = list(set(account[2:]))
            for i in range(len(account)):
                uf.add((name,account[i]))
                uf.merge((name,master),(name,account[i]))
        
        res = []
        for key,value in uf.father.items():
            # 是根节点
            if not value:
                # 添加user
                usr = [uf.accounts[key][0][0]]
                acc = []
                # 添加账户
                for account in uf.accounts[key]:
                    acc.append(account[1])
                    
                res.append(usr + sorted(acc))
                
        return res