h****n 发帖数: 1093 | 1 给一个list of sentences, 然后找出一个pair,common words 最大。举例:
1. This is a good day
2. This is a bad day
3. That was good day
返回1和2,因为有四个common words |
j******a 发帖数: 55 | |
c***0 发帖数: 449 | 3 是不是根据每个words建立trie. 建立的同时标记是来自第几句话。并且更新和第几句
话有share。建好了trie也就知道答案了
【在 h****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给一个list of sentences, 然后找出一个pair,common words 最大。举例: : 1. This is a good day : 2. This is a bad day : 3. That was good day : 返回1和2,因为有四个common words
|
b*********t 发帖数: 170 | 4 trie建好之后只知道每个word在哪些sentence出现过,要知道哪两个sentence的共同
word最多,还是要再遍历一遍。而且还要考虑sentence里面有word重复的情况。
我用hashmap做了一下,复杂度是O(n^2 * k), n是sentence个数,k是sentence长度
。感觉应该有更快的算法。
【在 c***0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是不是根据每个words建立trie. 建立的同时标记是来自第几句话。并且更新和第几句 : 话有share。建好了trie也就知道答案了
|
f******n 发帖数: 279 | |
o***g 发帖数: 2784 | 6 这样行么?
以每个单词做索引,值是出现在第几个句子。需要所有句子轮一圈:
This: 1, 2
good: 1, 3
....
以句子序号pair做索引,值是计数。每个单词后面的所有序号做全排列:
1, 2 : 4
1, 3 : 0
2, 3 : 2
.....
最后轮一圈上面的数据,找到最大的。
这个复杂度是多少?
【在 h****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给一个list of sentences, 然后找出一个pair,common words 最大。举例: : 1. This is a good day : 2. This is a bad day : 3. That was good day : 返回1和2,因为有四个common words
|
s*******y 发帖数: 45 | 7 我写了下code, http://codepad.org/bqm91IMF
不知道这个思路对不对啊?
有什么好办法实现提取一个sentence里面的words吗?面试中需要写这吗? |
p********n 发帖数: 165 | 8 用rabin-carp的方法 可以把每个单词都hash成一个数字,这样比较起来比较快,
至少可以优化成 O(n^2*m) m是平均每个句子里单词的个数, 稍微好一些。
另外一个优化: hash 每个句子的单词的时候,统计每个句子的单词数,并按照单词数
排序O(nlog(n))
这样,可以从第二最长的句子开始往后循环, 每次循环,假设到了第i个句子,要和所
有1...i-1的句子比,如果到目前为止share的单词数最大的solution >= 第i个句子的
整个单词数的时候,就可以中止程序。 算是一个early termination.
【在 b*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : trie建好之后只知道每个word在哪些sentence出现过,要知道哪两个sentence的共同 : word最多,还是要再遍历一遍。而且还要考虑sentence里面有word重复的情况。 : 我用hashmap做了一下,复杂度是O(n^2 * k), n是sentence个数,k是sentence长度 : 。感觉应该有更快的算法。
|
j*******p 发帖数: 73 | |
s******y 发帖数: 936 | |
x******0 发帖数: 178 | 11 用了inverted index之后不是还要用O(N^2×t) 遍历所有的pair和word,t是word数
目,吗? |
o***g 发帖数: 2784 | 12 看我给的思路
其实是mapreduce的思路
当然我的办法不一定是最优的,或者最可行的,思路大概就这样
【在 x******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用了inverted index之后不是还要用O(N^2×t) 遍历所有的pair和word,t是word数 : 目,吗?
|
S******1 发帖数: 216 | 13 取每个单词为一个维度,如果有n个单词那每个句子都是一个n维的vector [0,0,1,1,0
...1,0], 定义vector的距离就是都为1的维度的个数,找距离最近的pair.
是不是可以用类似于聚类的算法做近似计算? |
x*******9 发帖数: 138 | 14 设n个string,每个string有m个单词。
最暴力的方法不就是n**2次比较,每次比较的时间复杂度为O(m)
所以总时间复杂度为O(n**2 * m)
LS大大们说的方法貌似没有超过这个纯暴力的吧。。。 |