z*c
2 楼
m*a
3 楼
给每一个单词建一个数组记录在文件出现的所有位置。比如第5个字符开始就记录5.
这样有：
“aba”：3,8,20
“cds": 1,12,56
....
数组都是递增的。
然后问题就变成了： 在每个数组中找一个数字，使得这些数字中最小的和最大的距离
最小。复杂度是O(n);
这样有：
“aba”：3,8,20
“cds": 1,12,56
....
数组都是递增的。
然后问题就变成了： 在每个数组中找一个数字，使得这些数字中最小的和最大的距离
最小。复杂度是O(n);
b*1
4 楼
弱弱问 ： 纹凤姐身上，也能漂亮吗？
i*h
5 楼
这个O(n)你怎么做的?
【在 m**a 的大作中提到】
: 给每一个单词建一个数组记录在文件出现的所有位置。比如第5个字符开始就记录5.
: 这样有：
: “aba”：3,8,20
: “cds": 1,12,56
: ....
: 数组都是递增的。
: 然后问题就变成了： 在每个数组中找一个数字，使得这些数字中最小的和最大的距离
: 最小。复杂度是O(n);
【在 m**a 的大作中提到】
: 给每一个单词建一个数组记录在文件出现的所有位置。比如第5个字符开始就记录5.
: 这样有：
: “aba”：3,8,20
: “cds": 1,12,56
: ....
: 数组都是递增的。
: 然后问题就变成了： 在每个数组中找一个数字，使得这些数字中最小的和最大的距离
: 最小。复杂度是O(n);
I*t
6 楼
等老了皮肤松弛后再看
【在 z**c 的大作中提到】
【在 z**c 的大作中提到】
m*a
7 楼
这个n是单词数,扫描一遍文件是O(n).
这是哪个公司的题？
这是哪个公司的题？
o*c
8 楼
...
看成了漂亮的taco...
【在 z**c 的大作中提到】
看成了漂亮的taco...
【在 z**c 的大作中提到】
m*a
9 楼
扫描一遍数组应该也是线性的复杂度。
i*h
10 楼
G
【在 m**a 的大作中提到】
: 这个n是单词数,扫描一遍文件是O(n).
: 这是哪个公司的题？
【在 m**a 的大作中提到】
: 这个n是单词数,扫描一遍文件是O(n).
: 这是哪个公司的题？
i*h
11 楼
"在每个数组中找一个数字，使得这些数字中最小的和最大的距离最小"
怎么弄?
【在 m**a 的大作中提到】
: 扫描一遍数组应该也是线性的复杂度。
怎么弄?
【在 m**a 的大作中提到】
: 扫描一遍数组应该也是线性的复杂度。
m*a
12 楼
假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
pointer。重复知道所有pointer都指向数组末。
值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
pointer。重复知道所有pointer都指向数组末。
i*h
13 楼
好象是这样
code很麻烦啊
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
code很麻烦啊
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
m*a
14 楼
要写的话好像是很麻烦。 这个是onsite时被问的吗？
l*a
15 楼
结束条件不对
应该是某次最小的移到了数组末
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
应该是某次最小的移到了数组末
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
i*h
16 楼
N年以前的滑铁卢
【在 m**a 的大作中提到】
: 要写的话好像是很麻烦。 这个是onsite时被问的吗？
【在 m**a 的大作中提到】
: 要写的话好像是很麻烦。 这个是onsite时被问的吗？
m*a
17 楼
同意。那时候应该结束了，没有必要再找了。
【在 l*****a 的大作中提到】
: 结束条件不对
: 应该是某次最小的移到了数组末
【在 l*****a 的大作中提到】
: 结束条件不对
: 应该是某次最小的移到了数组末
b*b
18 楼
还是不太理解，牛人能给再解释一下不
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
p*2
19 楼
向后指向n个数中最小的那个的
pointer。
判断这个还是O（N）吗？
【在 m**a 的大作中提到】
: 假设有n个数组。 每个数组设一个pointer 指向开始。计算n个书中的最小距离（最大
: 值减最小值），如果比global的小，更新global。向后指向n个数中最小的那个的
: pointer。重复知道所有pointer都指向数组末。
z*t
20 楼
是的。指向当前的最小下标的指针向后移动之后，
需要遍历所有的指针才能找到新的最小下标。
如果整个文本的长度是n，目标单词有k个，
只能做到O(n)+O(k^2)，优化后可实现O(n) + O(k*logk)，
但做不到O(n)。
当然，由于通常情况下n >> k，
这个时候可以近似认为效率是O(n)。
不知道我的理解是不是正确的......
【在 p*****2 的大作中提到】
:
: 向后指向n个数中最小的那个的
: pointer。
: 判断这个还是O（N）吗？
需要遍历所有的指针才能找到新的最小下标。
如果整个文本的长度是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
21 楼
这题没读明白，啥叫“最小的包含所有搜索单词的段落”，完整1个段落同时size最小
？
？
相关阅读
临床试验 (转载)我这辈子最香艳的时候Re: 传习近平允诺有病即退位 (转载)华为/中兴等等在美的中国公司为什么 (转载)这个西安交大武大咋回事 (转载)老婆掏钱让外面找妹纸，美女套路深呀碰到个下悬月搞笑图片厉害了我的国紧急停播了 (转载)古生物学者研究发现：生物生殖器越大 灭绝越快Re: 求有经验GA 华人criminal defense lawyer (转载)中最赢 (转载)已知黄海波身高一米七，得出姚明最多一米八二Re: 世界上有没有哪个国家是被另一个国家完全包裹起来的？ (转贾跃亭老师你们还不懂吗？中延院学员赴习总书记插队的梁家河村过集体政治生日 (转载)没想到欣赏贾跃亭的大佬这么多搞笑动图：这是什么节目？感觉挻好看的长颈鹿的智商可能太低 (转载)搞笑动图：群演太不给力了，跑得不够快！