LeetCode 721. Accounts Merge

原题

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.
Example 1

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: 
The first and third John's are the same person as they have the common email "johnsmith@mail.com".
The second John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], 
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

题目大意

给出一个账户列表,其中每一个账户由多个字符串组成,第一个字符串为姓名,其余的字符串为在该姓名下注册的邮箱地址。由于同一个人可能有两个不同的账户,判别是否是同一个人所拥有的账户方法就是在不同的账户中发现是否有相同的邮箱地址,如果有相同的邮箱地址,则可判定两个账户为同一人所拥有。现在要做的就是,对给定账户列表中同一个人所拥有的账户进行合并,合并结果为一个人只拥有一个账户,并且该账户包含其所有的邮箱并且不重复。
Note:同一人的账户可能有多个重名邮箱地址,输出的时候要对这部分进行处理去掉冗余部分,并且进行字典序排列。

例如:

输入:
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"]]

输出:
[["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]

分析:因为第一个和第三个账户有重叠的部分,因此将它两合并。

分析

这个问题本质上是对不同的集合进行处理,因此暴力求解法在这里几乎不可能成功。求解这个问题的方法最经典的思路就是并查集。

并查集

上文中提到了并查集,然后这里简单的介绍一下并查集的思想和算法。

不相交的数据结构

具体的场景可以描述为S1, S2...Sn是n个不同的元素,我们要将它们分成n个不相交的集合,运用到此问题的场景可以有计算图中的连通分量等等。

这里说的太抽象,举个例子说明一下:

image

上图中,共有5个顶点, 其中A,B,C,F四个顶点构成一个强连通图,那么在进行集合划分的时候,我们就可以按照“是否构成强连通图的标准进行划分”,因此上图的顶点可以划分为两个不相交的集合,{ A, B, C, F}和{ D}两个集合。

基本的算法思想:

  1. 针对每一个集合选取出一个代表元素,它可以是这个集合中的某个元素。
  2. 提供一个方法find(x),属于同一集合的元素在使用此方法时,返回代表元素(如x, y属于同一集合,则find(x)和find(y)返回该集合的代表元)
  3. 提供一个方法same(x, y),返回x,y是否属于同一集合
  4. 提供一个方法union(x,y),将包含x,y元素的两个集合合并。将原来的$S_x, S_y$合并成$S_x\cup S_y$。对于此步骤,我们常用的方法是将一个集合的元素放到另一个集合中。

例子:

image

如上图所示,{ A, B, C}构成一个集合(这里我们把是否有边相连作为划分集合的标准),D 、 F分别构成一个集合,每个元素均保存一个指针,指向父元素。

  1. 其中,我们把三个集合的代表元素指定为:C,D, F。
  2. 在上一步的基础下,我们进行find(A)操作的时候,返回的元素为C, find(D)操作的时候,返回的元素为D。
  3. 在进行union(A, D)的时候,合并的情况不止一种,下图是一种情况:


    image

这样, find(D)方法返回的就是C元素。

上面的方法很方便的对集合的操作进行了定义,但是,一些操作太过于浪费时间,如find(D)方法,就需要依次遍历D,B来找到集合的代表元素,但是,在很多情况中,只需要每个元素保存集合的代表元素就够了,保存父节点的意义不是很大。因此,我们可以对上图做一个改进:每个元素的指针只指向所在集合的代表元素,对上图做了修改,改为下图。这样会使得查询操作更加简洁快速。

image

数据结构的表示

在算法导论21章中,提供链表的表示方法,然而我们这里使用最常用简单的方法,即,使用数组来进行每个元素之间的联系。

  1. 对于第一步,对于每个元素创造一个集合。
    Note:始终要记住一点,par[x]中存的是x所在集合的代表元素
//假设有n个元素,将每个元素初始化为其本身,即,可以抽象的看成每个元素是一个集合,代表元是自己。
int par[n];
for(int i = 0; i<n; i++)
    par[i] = i;
  1. find方法,寻找代表该元素所在集合中的代表元素。
//始终要记住一点,par[x]中存的是x所在集合的代表元素,而且在初始化的时候,par初始化为指向自己
//因此,在par[x] != x的时候,我们要做的是找到x所在集合的代表元素,修改指向代表元素的指针并返回(这步的意义在接下来union的例子中可以看到)。
int find(int x) 
{
    return par[x] == x ? x : (par[x] = find(x));
}
  1. same方法
    find方法,返回x,y是否属于同一个集合
//par[x]中存储的是代表元素的下标
bool same(int x, int y) 
{
    return par[x] == par[y];
}
  1. union方法

合并x,y所在元素的集合,Sx, Sy

//如果x, y所在的集合代表元素不同,那么对两个集合进行合并,合并的方法就是将其中一个集合的代表元素,指向另一个集合的代表元素,看到这里大家可能有点懵。下面画个图解释下
void union(int x, int y)
{
    int x = find(x);
    int y = find(y);
    if( x == y )
        return;
    par[x] = y;
}

Example:

image

上面的图中,在进行union(A, E)操作之后,变成下面的图:

image

这个时候,顶点$A,B,C,D$均不直接指向代表元素,但可以在后续的过程中,使用find(A)等等查询操作,一步步将存储的数据结构修改成如下:

image

到这里的我们就把整个并查集的方法过了一遍了,在一般使用的过程中,常把这几个函数定义为全局函数或者封装到一个类中来进行使用。

与具体问题相结合

那么在本题所涉及的条件下,我们应该满足两个要求。

  • 去除重复元素,并且有序排序

对于这个条件,很容易想到set集合(结合中没有重复元素,而且元素在插入的时候保持字典序),因此在实现的过程中,必要的一步就是将原有的邮箱列表装载到一个set集合中,然后进行如下的操作。

  • 对含有相同元素的集合,进行合并。

这个步骤中,就要我们的刚学的并查集登场了。

  1. 首先初始化并查集,使并查集和中的元素(i = 0,1,2...n)与account中的元素(account[0], account[1]...account[n])一一对应。
  2. 在对应结束后,我们便可以将所有的集合元素遍历一遍,判断哪些集合会有相同的元素。凡是有相同邮箱的账户均合并(此操作在并查集中实现)。
  3. 进行完上面的步骤之后,哪些account是属于同一人的,这些关系均会在并查集上体现出来。最后,我们按照并查集的操作,来将元素进行合并即可。

他山之石,可以攻玉(别人的答案)

在提交之后可以看到别人提交的答案,看完后再看看自己的代码便更觉得羞涩难挡,因此去掉了贴自己代码这一步,转而分析别人代码。
挑选了一个提交时间较快的代码(19min22s)来进行分析。

作者@shancha

const int N = 1000 + 5;
int n, par[N];
int find(int x) {
    return par[x] == x ? x : (par[x] = find(par[x]));
}
void unit(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    par[x] = y;
}
bool same(int x, int y) {
    return find(x) == find(y);
}
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        n = accounts.size();
        for (int i = 0; i < n; i++) par[i] = i;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) if (!same(i, j)) {
                for (int k = 1; k < accounts[i].size(); k++) for (int t = 1; t < accounts[j].size(); t++) {
                    if (accounts[i][k] == accounts[j][t]) unit(i, j);
                }
            }
        }
        vector<set<string> > res; res.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = find(i);
            for (int j = 1; j < accounts[i].size(); j++) res[par[i]].insert(accounts[i][j]);
        }
        vector<vector<string> > ret;
        for (int i = 0; i < n; i++) if (par[i] == i) {
            vector<string> cur;
            cur.push_back(accounts[i][0]);
            for (auto str : res[i]) cur.push_back(str);
            ret.push_back(cur);
        }
        return ret;
    }
};

分析:

  • 作者使用全局的数组来进行并查集操作
  • 但是在建立集合的操作中,并没有充分利用条件(如,仅当两个账户名相同时,才有两个账户同属于一个人的可能,即,如果两个账户名不同,则没有继续比较邮箱账号的必要)
  • 其余的算法流程使用并查集的思想就可以很好的理解了:一个账户表示一个元素,初始状态为n个账户,然后对账户的邮箱账号进行遍历,如果有相同的账号,则这两个账户属于同一个集合,接下来申请vector< set < string>> 空间来进行中间赋值管理,将属于同一集合的账户合并。最后整理返回。

Note:vector< set < string> > res; res.resize(n);中使用到了resize(n)函数,相当于new动态申请元素的空间, 即初始化n个元素的变量作用,如果没有这个操作,在接下来直接访问的时候会出错。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,657评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,662评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,143评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,732评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,837评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,036评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,126评论 3 410
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,868评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,315评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,641评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,773评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,470评论 4 333
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,126评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,859评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,095评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,584评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,676评论 2 351

推荐阅读更多精彩内容