92ms beats 92.12% with union find


  • 0
    E
    For example:
    data:{name1,mail1,mail2},{name1,mail1,mail3},{name1,mail4},{name2,mail5}
    
    DATA structure:
    hash:
     key   value(key)   value(value)
    name1    mail1         id1
             mail2         id1
             mail3         id2
             mail4         id3
    name2    mail5         id4
    
    idx:
    id: id1 id2 id3 id4
        id1 id1 id3 id4
    
    typedef map<string,int> mtype;
    class Solution {
    public:
        vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
            map<string,mtype >hash;
            vector<pair<int,int> >idx;
            for(int i=0;i<accounts.size();i++){//for1
                string name=accounts[i][0];
                idx.push_back(pair<int,int>(i,1));
                bool f=(hash.find(name)==hash.end());
                for(int j=1;j<accounts[i].size();j++){//for2
                    string mail=accounts[i][j];
                    if(f)hash[name][mail]=i;
                    else{//else1
                        mtype::iterator it=hash[name].find(mail);
                        if(it==hash[name].end())hash[name][mail]=i;
                        else{
                            int id1=find(it->second,idx),id2=find(i,idx);
                            if(idx[id1].second<idx[id2].second){
                                idx[id1].first=id2;
                                idx[id2].second+=idx[id1].second;
                            }else{
                                idx[id2].first=id1;
                                idx[id1].second+=idx[id2].second;
                            }
                        }
                    }//else1
                }//for2
            }//for1
            vector<vector<string> >res;
            for(auto it=hash.begin();it!=hash.end();it++){
                map<int,int>hasht;
                for(auto it2=it->second.begin();it2!=it->second.end();it2++){
                    int id=find(it2->second,idx);
                    if(hasht.find(id)==hasht.end()){
                        res.push_back(vector<string>{it->first,it2->first});
                        hasht[id]=res.size()-1;
                    }else res[hasht[id]].push_back(it2->first);
                }
            }
            return res;
        }//func
        int find(int id,vector<pair<int,int> >&idx){
            while(id!=idx[id].first){
                idx[id].first=idx[idx[id].first].first;
                id=idx[id].first;
            }
            return id;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.