假设有一个单词集,我想根据他们的char包(multiset)对它们进行聚类.例如
{茶,吃,阿巴,阿巴,你好}
将聚集成
{{tea,eat},{abba,aabb},{hello}}.
abbaaabb由于它们具有相同的char包,即两个a和两个,因此聚集在一起b.
为了使它高效,我能想到的一种天真的方式是将每个单词转换成一个char-cnt系列,例如,abba并且aabb将被转换为a2b2,tea/eat将被转换为a1e1t1.这样我就可以构建一个字典并用相同的键组合单词.
这里有两个问题:首先我必须对字符进行排序以构建密钥; 第二,字符串键看起来很笨拙,性能不如char/int键.
有没有更有效的方法来解决问题？
我被问到如何在社交网络中找到"发布者"的问题.假设(简化的)社交网络仅在两个用户之间具有"跟随"关系,并且一个人不能跟随他自己.然后我们将"发布者"定义为所有其他用户都遵循但不跟随任何人的用户.
更具体地,给定这种邻接矩阵格式的社交网络图,例如NxN布尔矩阵,其中cell [i,j]指示用户i是否跟随用户j.如何找出出版商.
我可以看到,最多只有一个发布者可以存在.(很容易证明:由于发布者后面跟着其他人,所以其他人都至少跟踪一个用户,所以他们不是发布者).我想出了一个天真的解决方案:首先逐列扫描,如果有一个全真列j(当然除了单元格[j,j]),则扫描行[j]以确保它全部为假.
显然,对于朴素算法,性能是O(n ^ 2),因为我们扫描整个矩阵.但是,我被告知有一个O(n)解决方案.我有点困在O(n).任何提示？