題目描述:給定一個帳號列表,每個帳號的第一個元素是帳號名稱,其餘元素是電子郵件地址。如果兩個帳號共享任何一個電子郵件地址,則這兩個帳號屬於同一個人。請將所有屬於同一人的帳號合併,並回傳合併後的結果,每個帳號內的電子郵件須依字母順序排列。
解題思路:
這道題的核心在於「連通性」的判斷:只要兩個帳號共享一個 email,它們就是同一個人,即使這個人可能透過「鏈式關聯」才相連(A 和 B 共享 email1,B 和 C 共享 email2,所以 A、B、C 都是同一個人)。
方法:Union-Find(並查集)
email_to_id):對每個帳號的每個 email,若該 email 第一次出現,記錄它屬於哪個帳號索引;若已出現過,則將當前帳號與先前的帳號進行 union(合併)。find() 取得其根帳號索引,將 email 歸集到對應的根帳號下。為什麼用 Union-Find 而非 DFS?
Union-Find 的優點是增量式合併,不需要先建立完整的圖再遍歷。每次遇到重複 email 就立刻 union,時間複雜度接近線性(含路徑壓縮和按秩合併)。DFS 方法也可行,但需要先建圖(email 為節點,同帳號的 email 互相連接),再進行 DFS 找連通分量,兩種方法的最終複雜度相似。
時間複雜度:O(N * K * α(N) + N * K * log(K)) — 其中 N 是帳號數量,K 是每個帳號平均的 email 數量。建立映射和執行 union 操作需要 O(N * K * α(N)),其中 α 是 Ackermann 函數的反函數(幾乎等於常數);最後對每組 email 排序需要 O(total_emails * log(total_emails)),整體約為 O(N * K * log(K))。
空間複雜度:O(N + M) — N 為帳號數量(Union-Find 陣列),M 為所有不重複 email 的總數(emailToId 映射)。
1. Initialize Union-Find with n nodes (one per account) 2. Create emailToId map 3. For each account i, for each email in accounts[i][1:]: a. If email in emailToId: union(i, emailToId[email]) b. Else: emailToId[email] = i 4. Create rootToEmails map 5. For each (email, id) in emailToId: a. root = find(id) b. rootToEmails[root].append(email) 6. For each (root, emails) in rootToEmails: a. Sort emails b. Prepend accounts[root][0] (name) c. Append to result 7. Return result
DFS 圖遍歷 O(N * K * log(K)):將每個 email 視為圖節點,同一帳號內的所有 email 兩兩相連(或星狀連接到第一個 email)。接著對所有 email 節點進行 DFS,找出每個連通分量,即為同一人的 email 集合。這個方法較直觀,但需要先建圖再遍歷,程式碼稍長。
BFS 圖遍歷 O(N * K * log(K)):與 DFS 方法相同,差異僅在用 BFS(隊列)代替 DFS(遞迴或棧)遍歷連通分量。在 email 數量龐大時,BFS 能避免遞迴深度過深導致的 stack overflow 問題。