721.账户合并

链接：721.账户合并
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、数组、哈希表、字符串、排序
简介：给定一个列表 accounts，合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按字符 ASCII 顺序排列的邮箱地址。账户本身可以以任意顺序返回。

题解 1 - typescript

• 编辑时间：2021-05-01
• 执行用时：272ms
• 内存消耗：53.2MB
• 编程语言：typescript
• 解法介绍：并查集。

class UnionFind {
  elements: number[];
  constructor(public size: number) {
    this.elements = new Array(size).fill(0).map((_, i) => i);
  }
  same(v1: number, v2: number): boolean {
    return this.find(v1) === this.find(v2);
  }
  find(v: number): number {
    return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
  }
  union(v1: number, v2: number): void {
    const e1 = this.find(v1);
    const e2 = this.find(v2);
    if (e1 !== e2) {
      this.elements[e1] = e2;
      this.size--;
    }
  }
}
function accountsMerge(accounts: string[][]): string[][] {
  const indexMap = new Map<string | number, number | string>();
  const nameMap = new Map<string, string>();
  let size = 0;
  for (const [name, ...emails] of accounts)
    emails.forEach(email => {
      if (!indexMap.has(email)) {
        indexMap.set(email, size);
        indexMap.set(size, email);
        size++;
      }
      nameMap.set(email, name);
    });
  const uf = new UnionFind(size);
  for (const [, ...emails] of accounts) {
    for (let i = 1, l = emails.length; i < l; i++) {
      uf.union(indexMap.get(emails[i]) as number, indexMap.get(emails[i - 1]) as number);
    }
  }
  const cache = new Map<number, number[]>();
  for (let i = 0; i < size; i++) {
    const index = uf.find(i);
    let list = cache.get(index);
    if (!list) cache.set(index, (list = []));
    list.push(i);
  }
  const emailSort = (email1: string, email2: string): number => {
    let i = 0;
    const len = Math.min(email1.length, email2.length);
    while (i < len) {
      if (email1[i] === email2[i]) i++;
      else return email1.codePointAt(i)! - email2.codePointAt(i)!;
    }
    return email1[i] === undefined ? -1 : 1;
  };
  const ans: string[][] = [];
  for (const [k, v] of cache.entries()) {
    ans.push([
      nameMap.get(indexMap.get(k) as string) as string,
      ...v.map(i => indexMap.get(i) as string).sort(emailSort),
    ]);
  }
  return ans;
}

题解 2 - python

• 编辑时间：2024-07-15
• 执行用时：1584ms
• 内存消耗：19.45MB
• 编程语言：python
• 解法介绍：并查集合并数据。

class UnionFind:
    def __init__(self, n) -> None:
        self.n = n
        self.data = [i for i in range(0, n)]
        self.sizes = [1] * n
        self.cnt = n
    def size(self, v: int) -> int:
        return self.sizes[self.find(v)]
    def find(self, v: int) -> int:
        if self.data[v] != v:
            self.data[v] = self.find(self.data[v])
        return self.data[v]
    def uni(self, v1: int, v2: int):
        p1 = self.find(v1)
        p2 = self.find(v2)
        if p1 != p2:
            self.sizes[p1] += self.sizes[p2]
            self.cnt -= self.sizes[p2]
            self.data[p2] = p1
    def same(self, v1: int, v2: int):
        return self.find(v1) == self.find(v2)
    def get_items(self) -> List[List[int]]:
        map = defaultdict(list)
        for i in range(self.n): map[self.find(i)].append(i)
        return map.values()
class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        n = len(accounts)
        uf = UnionFind(n)
        for i in range(n):
            name1 = accounts[i][0]
            emails1 = set(accounts[i][1:])
            for j in range(i):
                name2 = accounts[j][0]
                emails2 = set(accounts[j][1:])
                if name1 == name2 and not emails1.isdisjoint(emails2):
                    uf.uni(i, j)
        res = []
        for arr in uf.get_items():
            item = []
            res.append(item)
            item.append(accounts[arr[0]][0])
            emails = []
            for idx in arr: emails += accounts[idx][1:]
            item += sorted(set(emails))
        return res