【问题】一道面试题~

2017/9/16镜像同步5 回复

命题：选择一个算法，以最低复杂度来实现两个集合之间的相似度计算举例：集合A (a,b,c,d,e)，集合B (b,e,f,a,c,j,k），A和B之间一致元素为a,b,c,e。A的相似度为4/5，B的相似度为4/7。两个集合的数量级通常为万级，最大为百万级，元素无序存储

订阅后，新回复会通过你的通知中心匿名送达。

5 条回复

ym19940508机器人#1 · 2017/9/16

把A的每一个放进set，在去遍历B的每一个元素看set里面有没有。。这样可以把，但不知道有没有更优解

nanguohao机器人#2 · 2017/9/16

如果是时间复杂度的话，对两个AB分别排序，假如说用n*logn的排序算法（例如快速排序，或者随即快速排序），那么排序需要花费2*n*logn,(不失一般性假设A，B大小相同)，排序完成后可以再线性时间n内找出两个集合的相似元素个数，所以总的时间复杂度应该是n*logn。如果A，B中的数据有特殊分布，可以使用计数排序等时间复杂度为n的排序算法的话，那么总的复杂度应该在线性时间内n完成。

a940100079机器人#3 · 2017/9/16

看你选择时间优先，还是空间优先了楼上都说的挺对的

qwerabc机器人#4 · 2017/9/16

他最后强调了数据量，不需要考虑海量数据的处理吗【在 nanguohao 的大作中提到: 】 : 如果是时间复杂度的话，对两个AB分别排序，假如说用n*logn的排序算法（例如快速排序，或者随即快速排序），那么排序需要花费2*n*logn,(不失一般性假设A，B大小相同)，排序完成后可以再线性时间 : ......... 发自「贵邮」

nanguohao机器人#5 · 2017/9/16

【在 qwerabc 的大作中提到: 】 : 他最后强调了数据量，不需要考虑海量数据的处理吗 : : 发自「贵邮」额，还没参加过面试，不知道它最后强调数据量的用意，不过如果不是大数据量的话，进行优化没有太大的意义