自学内容网 自学内容网

[M并查集] lc721. 账户合并(并查集+并查集变种+dfs+建图+好题)

1. 题目来源

链接:721. 账户合并

2. 题目解析

睡不着,做做题。
本题很明显看出,一个名称像一个集合,集合元素是所有的邮箱,一个集合和其他集合要合并的前提是,集合内有相同元素。于是引发下面两个思路:

  • 集合合并:并查集
  • 建图深搜:dfs

不想看这个 dfs 的做法,关于本题 并查集 的做法还是挺有意思的。

  • 将每一行初始元素单独看成集合,一开始所有的集合未经合并,都是独立的,用下标表示集合。
  • 用每一个 email,做 hash,统计相同 email 的集合有哪些,用 vector 统计出来。
  • 这时候就可以用并查集进行集合合并了,将 vector 中大于两个元素的所有集合统一合并起来。更改并查集的父节点存储值,也是集合合并的核心操作。
  • email 数据整理。相同集合的 email 用 set 进行累计、去重、排序。
  • 结果输出,这个时候一些集合是没有结果的,要特判一下,也不需要对结果进行排序,直接输出即可。

  • 时间复杂度 O ( n ) O(n) O(n)
  • 空间复杂度 O ( 1 ) O(1) O(1)

class Solution {
   
public:
    vector<int> p;

    int find(int x) {
      // 并查集默写函数
        if (p[x] != x) return find(p[x]);

        return p[x];
    }

    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
   
        int n = accounts.

原文地址:https://blog.csdn.net/yl_puyu/article/details/140426458

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!