一、题目
1、题目描述
给定一个列表
accounts，每个元素accounts[i]是一个字符串列表，其中第一个元素accounts[i][0]是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。
2、接口描述
python3
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:cpp
class Solution {
public:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
}
};C#
public class Solution {
public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) {
}
}3、原题链接
二、解题报告
1、思路分析
由于有相同邮箱的账户是同一个人的账户，于是我们可以按照邮箱将每个账户编号合并，这可以用并查集来实现，然后把一个连通块的邮箱汇总排序即可
本题还有dfs做法，略
2、复杂度
时间复杂度： O(NlogN)空间复杂度：O(NlogN)
3、代码详解
python3
class UnionFindSet:
__slots__ = 'n', 'p'
def __init__(self, n: int):
self.n = n
self.p = [-1] * n
def find(self, x: int) -> int:
p = self.p
if p[x] < 0:
return x
p[x] = self.find(p[x])
return p[x]
def merge(self, x: int, y: int) -> None:
p = self.p
px, py = self.find(x), self.find(y)
if px == py:
return
if p[px] > p[py]:
px, py = py, px
p[px] += p[py]
p[py] = px
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
n = len(accounts)
ufs = UnionFindSet(n)
pre = {}
for i, (_, *emails) in enumerate(accounts):
for email in emails:
if email in pre:
ufs.merge(pre[email], i)
else:
pre[email] = i
g = defaultdict(set)
for i, (_, *emails) in enumerate(accounts):
g[ufs.find(i)].update(emails)
return [[accounts[i][0]] + sorted(emails) for i, emails in g.items()]cpp
struct UnionFindSet {
std::vector<int> p;
int n;
UnionFindSet(int _n) : p(_n, -1), n(_n) {}
int find(int x) {
return p[x] < 0 ? x : p[x] = find(p[x]);
}
void merge(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return;
if (p[px] > p[py]) std::swap(px, py);
p[px] += p[py], p[py] = px;
}
int size(int x) {
return -p[find(x)];
}
};
class Solution {
public:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
int n = accounts.size();
UnionFindSet ufs(n);
unordered_map<string, int> pre;
for (int i = 0; i < n; ++ i)
for (int j = 1; j < accounts[i].size(); ++ j)
if (pre.count(accounts[i][j]))
ufs.merge(i, pre[accounts[i][j]]);
else
pre[accounts[i][j]] = i;
unordered_map<int, unordered_set<string>> st;
for (int i = 0; i < n; ++ i)
st[ufs.find(i)].insert(accounts[i].begin() + 1, accounts[i].end());
vector<vector<string>> res;
for (auto& p : st) {
res.emplace_back();
res[res.size() - 1].emplace_back(accounts[p.first][0]);
for (auto& x : p.second)
res[res.size() - 1].push_back(x);
sort(res[res.size() - 1].begin() + 1, res[res.size() - 1].end());
}
return res;
}
};C#
public class UnionFindSet
{
private int[] p;
private int n;
public UnionFindSet(int _n)
{
n = _n;
p = Enumerable.Repeat(-1, n).ToArray();
}
public int find(int x)
{
return p[x] < 0 ? x : p[x] = find(p[x]);
}
public void merge(int x, int y)
{
int px = find(x), py = find(y);
if (px == py) return;
if (px > py)
(px, py) = (py, px);
p[px] += p[py];
p[py] = px;
}
}
public class Solution {
public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) {
int n = accounts.Count;
UnionFindSet ufs = new UnionFindSet(n);
IDictionary<string, int> pre = new Dictionary<string, int>();
for (int i = 0; i < accounts.Count; ++ i) {
for (int j = 1; j < accounts[i].Count; ++ j) {
if (pre.ContainsKey(accounts[i][j]))
ufs.merge(pre[accounts[i][j]], i);
else
pre.Add(accounts[i][j], i);
}
}
IDictionary<int, ISet<string>> st = new Dictionary<int, ISet<string>>();
for (int i = 0; i < accounts.Count; ++ i)
for (int j = 1; j < accounts[i].Count; ++ j) {
if (!st.ContainsKey(ufs.find(i)))
st.Add(ufs.find(i), new HashSet<string>());
st[ufs.find(i)].Add(accounts[i][j]);
}
IList<IList<string>> res = new List<IList<string>>();
foreach (var p in st) {
IList<string> a = new List<string>();
foreach (var s in p.Value)
a.Add(s);
((List<string>)a).Sort(string.CompareOrdinal);
a.Insert(0, accounts[p.Key][0]);
res.Add(a);
}
return res;
}
}
