LeetCode 721.账户合并 - JavaScript

题目描述力扣(LeetCode)

给定一个列表 accounts,每个元素 accounts[i]  是一个字符串列表,其中第一个元素 accounts[i][0]  是名称 (name),其余元素是 emails 表示该帐户的邮箱地址。

现在,我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址,则两个帐户必定属于同一个人。请注意,即使两个帐户具有相同的名称,它们也可能属于不同的人,因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户,但其所有帐户都具有相同的名称。

合并帐户后,按以下格式返回帐户:每个帐户的第一个元素是名称,其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。

Input:
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation:
  第一个和第三个 John 是同一个人,因为他们有共同的电子邮件 "johnsmith@mail.com"。
  第二个 John 和 Mary 是不同的人,因为他们的电子邮件地址没有被其他帐户使用。
  我们可以以任何顺序返回这些列表,例如答案[['Mary','mary@mail.com'],['John','johnnybravo@mail.com'],
  ['John','john00@mail.com','john_newyork@mail.com','johnsmith@mail.com']]仍然会被接受。

# 题目分析

题目提到,用户可能会重名,不能通过用户名判断用户,应该通过邮箱地址。并且一个用户由多个邮箱地址,要做的就是将同一个用户的多个邮箱地址合并到一起。

# 解法:并查集

借助并查集,整体的处理思路如下:

  1. 初始化并查集 uf。初始化映射 map,保存 email => username 的映射
  2. 遍历 accounts 中的每个列表 account
    • 从 account 列表的第 2 个元素开始遍历,将 email => username 保存到 map 中,将当前元素和下一个元素放入 uf 中
  3. 初始化映射 sets,保存 email => email[] 的映射。
  4. 循环遍历 map 的键,将属于同一连通分量(同一用户)的所有邮箱放入对应的列表中。
  5. 遍历 sets 的键和值,通过 map 可得到对应的 username,而值就是用户的所有邮箱。

由于 JavaScript 不存在并查集,所以需要 diy。整体代码如下:

// ac地址:https://leetcode-cn.com/problems/accounts-merge/
// 原文地址:https://xxoo521.com/2020-02-28-redundant-connection/

class UnionFind {
  constructor() {
    this.parent = new Map();
  }

  // 查找元素所在集合
  find(x) {
    while (this.parent.has(x)) {
      x = this.parent.get(x);
    }
    return x;
  }

  // 合并两个集合
  union(p, q) {
    const rootP = this.find(p);
    const rootQ = this.find(q);
    if (rootP !== rootQ) {
      this.parent.set(this.find(p), this.find(q));
    }
  }
}

const cmp = (x, y) => {
  if (x < y) return -1;
  if (x > y) return 1;
  return 0;
};

/**
 * @param {string[][]} accounts
 * @return {string[][]}
 */
var accountsMerge = function (accounts) {
  const uf = new UnionFind();
  const map = {}; // email => name

  // 步骤1:将属于同一集合的email进行“连线”
  for (const account of accounts) {
    for (let i = 1; i < account.length; ++i) {
      map[account[i]] = account[0];
      if (i < account.length - 1) {
        uf.union(account[i], account[i + 1]);
      }
    }
  }
  // 步骤2: 将属于同一连通分量(同一用户)的所有邮箱放入对应的列表中
  const sets = {}; // key: string; value: string[]
  for (const email in map) {
    const root = uf.find(email);
    if (!sets[root]) {
      sets[root] = [];
    }
    sets[root].push(email);
  }

  const res = [];
  for (const root in sets) {
    sets[root].sort(cmp);
    res.push([map[root], ...sets[root]]);
  }
  return res;
};

# 更多资料

若有错误,欢迎指正。若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇