Eisen 筆記

#721. Accounts Merge

題目描述

給你一個account列表，列表中的每個account[i]元素都是字串列表，字串列表中的第一個元素account[i][0]是名字，後面的元素則是帳號的email。

現在，我們想要合併這些帳號。兩個帳號的email如果有重複，則這兩個帳號是屬於同一個人的。但如果兩個帳號名字一樣，仍然有可能屬於不同的人但是剛好名字一樣。

每個人都有可能會有好幾個號，但是這些帳號的名字都會是一樣的。

合併完帳號列表後，回傳帳號列表並且將帳號用以下格式呈現：第一個元素為帳號名字，剩下的元素是被按照順序排列後的email。帳號可以以不同的順序排列。

限制條件

  1. 1 <= accounts.length <= 1000
  2. 2 <= accounts[i].length <= 10
  3. 1 <= accounts[i][j].length <= 30
  4. accounts[i][0]只會由英文字母組成。
  5. accounts[i][j](j > 0) 都是符合格式的email。

解題思路

題目說一個人有多組Email，而且可能會出現同時有好幾筆屬於同一個人的資料，想要合併這些資料，就必須確認資料是屬於同一個人的，因此兩筆資料之間必須要存在共同的Email，才能達成合併條件。

而在最一開始，我們不會知道哪些資料是相關的，所以最開始，先把個人資料劃分成一個Group，並且給Email加上一個Group的Tag用來區分，然後將Email放入Hashtable中作為檢查紀錄。

當處理到某個Email時，這個Email可能在過去曾經標記過了，我們可以在Hashtable的紀錄中找到，那麼這代表這個Email的所屬Group跟我們正在處理的Group是一樣的，所以我們在完成當前Group的同時，也要把記錄中的Email的Group所包含的其他Email都轉移到當前的Group中，這樣就完成了合併。

public class Solution {
    public class GroupNode{
        public int Num;
        public string Owner;
        public List<Email> mails;
        public GroupNode(int num, string owner){
            Num = num;
            Owner = owner;
            mails = new List<Email>();
        }
    }
    public class Email{
        public int Group;        
        public string Address;
        public Email(int group, string address){
            Group = group;            
            Address = address;
        }
    }
    public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) {
        int groupNum = 0;
        var nodes = new Hashtable();
        var recorded_mails = new Hashtable();
        foreach(var account in accounts){
            var node = new GroupNode(groupNum,account[0]);            
            for(int i=1;i<account.Count;i++){
                var mail = new Email(groupNum,account[i]);                
                if(recorded_mails.Contains(mail.Address)){
                    var num = ((Email) recorded_mails[mail.Address]).Group;
                    var prev_node = (GroupNode)nodes[num];
                    // if(num == groupNum) continue;
                    if(prev_node==null) continue;
                    foreach(var m in prev_node.mails){
                        m.Group = groupNum;
                        node.mails.Add(m);
                    }
                    nodes.Remove(num);
                }else{
                    recorded_mails.Add(mail.Address,mail);
                }
                if(node.mails.Find((ele)=>ele.Address==mail.Address) == null) node.mails.Add(mail);
            }
            nodes.Add(groupNum,node);
            groupNum++;
        }
        var ans = new List<IList<string>>();
        foreach(DictionaryEntry node in nodes){
            var group = (GroupNode)node.Value;            
            var accountName=group.Owner;
            var list = new List<string>();
            foreach(var i in group.mails) list.Add(i.Address);
            list.Sort((a,b)=>String.CompareOrdinal(a,b));
            list.Insert(0,accountName);
            ans.Add(list);
        }
        return ans;
    }
}

複雜度分析：

  • 時間複雜度：Account的數量為n，帳戶中最長的Account長度為m，所以總郵件數量為n * m，處理完合併後，還需要對所有郵件進行整理，會花費Log n * m的時間，因此時間複雜度為O(n * m * log n * m)。
  • 空間複雜度：會建立空間存放整理過後的帳戶與郵件，因此空間複雜度為O(n * m)。

學習重點

  • Disjoint Set Union (DSU)
Last Updated:
Contributors: eisen