i***h
发帖数: 12655 | 1 一个文本文件, 另外给n个搜索单词
要求找出最小的包含所有搜索单词的段落 |
m**a
发帖数: 139 | 2 给每一个单词建一个数组记录在文件出现的所有位置。比如第5个字符开始就记录5.
这样有：
“aba”：3,8,20
“cds": 1,12,56
....
数组都是递增的。
然后问题就变成了： 在每个数组中找一个数字，使得这些数字中最小的和最大的距离
最小。复杂度是O(n); |
i***h
发帖数: 12655 | 3 这个O(n)你怎么做的?
【在 m**a 的大作中提到】
: 给每一个单词建一个数组记录在文件出现的所有位置。比如第5个字符开始就记录5.
: 这样有：
: “aba”：3,8,20
: “cds": 1,12,56
: ....
: 数组都是递增的。
: 然后问题就变成了： 在每个数组中找一个数字，使得这些数字中最小的和最大的距离
: 最小。复杂度是O(n);
|
m**a
发帖数: 139 | 4 这个n是单词数,扫描一遍文件是O(n).
这是哪个公司的题？ |
m**a
发帖数: 139 | |
i***h
发帖数: 12655 | 6 G
【在 m**a 的大作中提到】
: 这个n是单词数,扫描一遍文件是O(n).
: 这是哪个公司的题？
|
i***h
发帖数: 12655 | 7 "在每个数组中找一个数字，使得这些数字中最小的和最大的距离最小"
怎么弄?
【在 m**a 的大作中提到】
: 扫描一遍数组应该也是线性的复杂度。
|
m**a
发帖数: 139 | 8 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
pointer。重复知道所有pointer都指向数组末。 |
i***h
发帖数: 12655 | 9 好象是这样
code很麻烦啊
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
|
m**a
发帖数: 139 | 10 要写的话好像是很麻烦。 这个是onsite时被问的吗？ |
|
|
l*****a
发帖数: 14598 | 11 结束条件不对
应该是某次最小的移到了数组末
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
|
i***h
发帖数: 12655 | 12 N年以前的滑铁卢
【在 m**a 的大作中提到】
: 要写的话好像是很麻烦。 这个是onsite时被问的吗？
|
m**a
发帖数: 139 | 13 同意。那时候应该结束了，没有必要再找了。
【在 l*****a 的大作中提到】
: 结束条件不对
: 应该是某次最小的移到了数组末
|
b******b
发帖数: 300 | 14 还是不太理解，牛人能给再解释一下不
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
|
p*****2
发帖数: 21240 | 15
向后指向n个数中最小的那个的
pointer。
判断这个还是O（N）吗？
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
|
z******t
发帖数: 59 | 16 是的。指向当前的最小下标的指针向后移动之后，
需要遍历所有的指针才能找到新的最小下标。
如果整个文本的长度是n，目标单词有k个，
只能做到O(n)+O(k^2)，优化后可实现O(n) + O(k*logk)，
但做不到O(n)。
当然，由于通常情况下n >> k，
这个时候可以近似认为效率是O(n)。
不知道我的理解是不是正确的......
【在 p*****2 的大作中提到】
:
: 向后指向n个数中最小的那个的
: pointer。
: 判断这个还是O（N）吗？
|
h********w
发帖数: 221 | 17 这题没读明白，啥叫“最小的包含所有搜索单词的段落”，完整1个段落同时size最小
？ |
