hiho一下第171周《Email Merge》题目分析

5
1

《Email Merge》题目分析

本题直接暴力的做法就是枚举两个用户名,然后比较这两个用户名是否存在相同的邮箱。存在的话就是同一个人:

mark[1 .. N] = false
for i = 1 .. N-1:
    if mark[i]:
        continue
    print username[i] //本组第一个用户名
    for j = i + 1:
        if share-same-email(i, j):
            mark[j] = true
            print username[j] + ' '
    print '\n'

这个算法的复杂度是O(N^2) x O(share-same-email的复杂度),很有可能超时。

下面我们介绍一个利用倒排索引+并查集的优化算法。

我们知道判断两个字符串A和B是否相等的复杂度是与字符串长度成正比的,要比比较两个整数是否相同的复杂度高。所以首先我们可以做的优化就是把用户名和邮箱都用hashmap映射到整数1, 2, 3 ... 上。这样比较就是O(1)的了。

输入给的数据是每个用户名对应哪些邮箱,我们利用倒排索引可以得到每个邮箱对应哪些用户名:

alice@hihocoder.com: alice
alice@gmail.com: alice alicetest
bob@qq.com: bob
alice@qq.com: alicetest alice2016

注意这里我们为了描述方便使用的还是字符串,实际上你的程序这时处理的应该是映射后的整数。

然后我们使用并查集把有相同邮箱的用户名合并到一个集合。注意由于输入的每个用户名最多10个邮箱,所以这里最多做O(10N)次合并。

最后我们要把所有的集合输出。注意这里还需要花费点代码保证输出顺序与题目要求一致。

4 answer(s)

1

我想我的代码是最丑的没有之一了,杯具

1

只过了40%的同学估计是每输入一组username和email address就加到最后结果了吧 我就是。。。=_=

2

我的做法是把名字和邮箱映射成点,然后找连通子图...

0

6 alice 2 alice@hihocoder.com alice@gmail.com
bob 1 bob@qq.com
alicebest 2 alice@gmail.com alice@qq.com
alice2016 1 alice@qq.com
bob 1 alice@qq.com
aaa 1 alice@qq.com

这组数据输出什么

write answer 切换为英文 切换为中文


转发分享