| comments | difficulty | edit_url | tags | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
|
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。
示例 1：
输入：accounts = [["John", "[email protected]", "[email protected]"], ["John", "[email protected]"], ["John", "[email protected]", "[email protected]"], ["Mary", "[email protected]"]] 输出：[["John", '[email protected]', '[email protected]', '[email protected]'], ["John", "[email protected]"], ["Mary", "[email protected]"]] 解释： 第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "[email protected]"。 第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。 可以以任何顺序返回这些列表，例如答案 [['Mary'，'[email protected]']，['John'，'[email protected]']， ['John'，'[email protected]'，'[email protected]'，'[email protected]']] 也是正确的。
示例 2：
输入：accounts = [["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]] 输出：[["Ethan","[email protected]","[email protected]","[email protected]"],["Gabe","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
提示：
1 <= accounts.length <= 10002 <= accounts[i].length <= 101 <= accounts[i][j].length <= 30accounts[i][0]由英文字母组成accounts[i][j] (for j > 0)是有效的邮箱地址
根据题目描述，我们可以使用并查集，将具有相同邮箱地址的账户合并在一起。
我们首先遍历所有的账户，对于第
接下来，我们遍历所有的账户，对于第
时间复杂度
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
uf = UnionFind(len(accounts))
d = {}
for i, (_, *emails) in enumerate(accounts):
for email in emails:
if email in d:
uf.union(i, d[email])
else:
d[email] = i
g = defaultdict(set)
for i, (_, *emails) in enumerate(accounts):
root = uf.find(i)
g[root].update(emails)
return [[accounts[root][0]] + sorted(emails) for root, emails in g.items()]class UnionFind {
private final int[] p;
private final int[] size;
public UnionFind(int n) {
p = new int[n];
size = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
size[i] = 1;
}
}
public int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
public boolean union(int a, int b) {
int pa = find(a), pb = find(b);
if (pa == pb) {
return false;
}
if (size[pa] > size[pb]) {
p[pb] = pa;
size[pa] += size[pb];
} else {
p[pa] = pb;
size[pb] += size[pa];
}
return true;
}
}
class Solution {
public List<List<String>> accountsMerge(List<List<String>> accounts) {
int n = accounts.size();
UnionFind uf = new UnionFind(n);
Map<String, Integer> d = new HashMap<>();
for (int i = 0; i < n; ++i) {
for (int j = 1; j < accounts.get(i).size(); ++j) {
String email = accounts.get(i).get(j);
if (d.containsKey(email)) {
uf.union(i, d.get(email));
} else {
d.put(email, i);
}
}
}
Map<Integer, Set<String>> g = new HashMap<>();
for (int i = 0; i < n; ++i) {
int root = uf.find(i);
g.computeIfAbsent(root, k -> new HashSet<>())
.addAll(accounts.get(i).subList(1, accounts.get(i).size()));
}
List<List<String>> ans = new ArrayList<>();
for (var e : g.entrySet()) {
List<String> emails = new ArrayList<>(e.getValue());
Collections.sort(emails);
ans.add(new ArrayList<>());
ans.get(ans.size() - 1).add(accounts.get(e.getKey()).get(0));
ans.get(ans.size() - 1).addAll(emails);
}
return ans;
}
}class UnionFind {
public:
UnionFind(int n) {
p = vector<int>(n);
size = vector<int>(n, 1);
iota(p.begin(), p.end(), 0);
}
bool unite(int a, int b) {
int pa = find(a), pb = find(b);
if (pa == pb) {
return false;
}
if (size[pa] > size[pb]) {
p[pb] = pa;
size[pa] += size[pb];
} else {
p[pa] = pb;
size[pb] += size[pa];
}
return true;
}
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
private:
vector<int> p, size;
};
class Solution {
public:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
int n = accounts.size();
UnionFind uf(n);
unordered_map<string, int> d;
for (int i = 0; i < n; ++i) {
for (int j = 1; j < accounts[i].size(); ++j) {
const string& email = accounts[i][j];
if (d.find(email) != d.end()) {
uf.unite(i, d[email]);
} else {
d[email] = i;
}
}
}
unordered_map<int, set<string>> g;
for (int i = 0; i < n; ++i) {
int root = uf.find(i);
g[root].insert(accounts[i].begin() + 1, accounts[i].end());
}
vector<vector<string>> ans;
for (const auto& [root, s] : g) {
vector<string> emails(s.begin(), s.end());
emails.insert(emails.begin(), accounts[root][0]);
ans.push_back(emails);
}
return ans;
}
};type unionFind struct {
p, size []int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
size := make([]int, n)
for i := range p {
p[i] = i
size[i] = 1
}
return &unionFind{p, size}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) bool {
pa, pb := uf.find(a), uf.find(b)
if pa == pb {
return false
}
if uf.size[pa] > uf.size[pb] {
uf.p[pb] = pa
uf.size[pa] += uf.size[pb]
} else {
uf.p[pa] = pb
uf.size[pb] += uf.size[pa]
}
return true
}
func accountsMerge(accounts [][]string) (ans [][]string) {
n := len(accounts)
uf := newUnionFind(n)
d := make(map[string]int)
for i := 0; i < n; i++ {
for _, email := range accounts[i][1:] {
if j, ok := d[email]; ok {
uf.union(i, j)
} else {
d[email] = i
}
}
}
g := make(map[int]map[string]struct{})
for i := 0; i < n; i++ {
root := uf.find(i)
if _, ok := g[root]; !ok {
g[root] = make(map[string]struct{})
}
for _, email := range accounts[i][1:] {
g[root][email] = struct{}{}
}
}
for root, s := range g {
emails := []string{}
for email := range s {
emails = append(emails, email)
}
sort.Strings(emails)
account := append([]string{accounts[root][0]}, emails...)
ans = append(ans, account)
}
return
}class UnionFind {
private p: number[];
private size: number[];
constructor(n: number) {
this.p = new Array(n);
this.size = new Array(n);
for (let i = 0; i < n; ++i) {
this.p[i] = i;
this.size[i] = 1;
}
}
find(x: number): number {
if (this.p[x] !== x) {
this.p[x] = this.find(this.p[x]);
}
return this.p[x];
}
union(a: number, b: number): boolean {
let pa = this.find(a),
pb = this.find(b);
if (pa === pb) {
return false;
}
if (this.size[pa] > this.size[pb]) {
this.p[pb] = pa;
this.size[pa] += this.size[pb];
} else {
this.p[pa] = pb;
this.size[pb] += this.size[pa];
}
return true;
}
}
function accountsMerge(accounts: string[][]): string[][] {
const n = accounts.length;
const uf = new UnionFind(n);
const d = new Map<string, number>();
for (let i = 0; i < n; ++i) {
for (let j = 1; j < accounts[i].length; ++j) {
const email = accounts[i][j];
if (d.has(email)) {
uf.union(i, d.get(email)!);
} else {
d.set(email, i);
}
}
}
const g = new Map<number, Set<string>>();
for (let i = 0; i < n; ++i) {
const root = uf.find(i);
if (!g.has(root)) {
g.set(root, new Set<string>());
}
const emailSet = g.get(root)!;
for (let j = 1; j < accounts[i].length; ++j) {
emailSet.add(accounts[i][j]);
}
}
const ans: string[][] = [];
for (const [root, emails] of g.entries()) {
const emailList = Array.from(emails).sort();
const mergedAccount = [accounts[root][0], ...emailList];
ans.push(mergedAccount);
}
return ans;
}