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 的大作中提到】
: 给一个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 的大作中提到】
: 是不是根据每个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 的大作中提到】
: 给一个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 的大作中提到】
: 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 的大作中提到】
: 用了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大大们说的方法貌似没有超过这个纯暴力的吧。。。 |
