r***u
发帖数: 83 | 1 现在搜索三个词，比如“hello”,"world",
"goodbye", 搜索完成之后会有三个array，每一个array都存放着三个词在一篇文章里
的位置。写一个函数，返回两个值，代表文章中的两个位置，在这两个位置之间，“
hello”,"world", "goodbye"至少各出现一次，而且要求这两个位置之间的距离尽可能
短。
我记得以前在版上看到有讨论这道题，可是我现在找不到了。 | c**y
发帖数: 172 | 2 Is this useful?
http://www.stevekrenzel.com/articles/blurbs
【在 r***u 的大作中提到】
: 现在搜索三个词，比如“hello”,"world",
: "goodbye", 搜索完成之后会有三个array，每一个array都存放着三个词在一篇文章里
: 的位置。写一个函数，返回两个值，代表文章中的两个位置，在这两个位置之间，“
: hello”,"world", "goodbye"至少各出现一次，而且要求这两个位置之间的距离尽可能
: 短。
: 我记得以前在版上看到有讨论这道题，可是我现在找不到了。
| r***u
发帖数: 83 | | p*u
发帖数: 136 | 4 我想到一个方法是这样的：
1，三个数组A，B，C分别保存3个单词的位置，假设是数组是升序的。
2，将三个数组合并为一个数组Z = A + B + C，合并后的数组Z也是升序的，然后在每
一个位置记录一下，这个位置是从A，或者B，还是C得来的。这个是线性的时间复杂度。
3，由于要求是3个单词至少出现一次。所以可以设计这样一个算法：
有两个指针begin和end，并记录begin和end这个区间内3个单词分别出现的次数。
最开始begin和end都指向Z的开端。然后end开始往后扫：当发现begin到end区间内
所有单词的次数都大于等于1的时候，找到了一个候选解。当发现把begin指针所在的单
词去掉之后，区间内这个单词的个数不会为0，则把begin指针向前移。
所有候选解中距离最短的一个，就是最后要找的解。
由于begin和end指针都是从Z的开端扫到Z的末端，所以时间复杂度也是线性的。
【在 r***u 的大作中提到】
: 现在搜索三个词，比如“hello”,"world",
: "goodbye", 搜索完成之后会有三个array，每一个array都存放着三个词在一篇文章里
: 的位置。写一个函数，返回两个值，代表文章中的两个位置，在这两个位置之间，“
: hello”,"world", "goodbye"至少各出现一次，而且要求这两个位置之间的距离尽可能
: 短。
: 我记得以前在版上看到有讨论这道题，可是我现在找不到了。
| g****n
发帖数: 431 | 5 这个办法比较好，也比较简单。如果in-place做还是有些难度的。
度。
【在 p*u 的大作中提到】
: 我想到一个方法是这样的：
: 1，三个数组A，B，C分别保存3个单词的位置，假设是数组是升序的。
: 2，将三个数组合并为一个数组Z = A + B + C，合并后的数组Z也是升序的，然后在每
: 一个位置记录一下，这个位置是从A，或者B，还是C得来的。这个是线性的时间复杂度。
: 3，由于要求是3个单词至少出现一次。所以可以设计这样一个算法：
: 有两个指针begin和end，并记录begin和end这个区间内3个单词分别出现的次数。
: 最开始begin和end都指向Z的开端。然后end开始往后扫：当发现begin到end区间内
: 所有单词的次数都大于等于1的时候，找到了一个候选解。当发现把begin指针所在的单
: 词去掉之后，区间内这个单词的个数不会为0，则把begin指针向前移。
: 所有候选解中距离最短的一个，就是最后要找的解。
| d****2
发帖数: 6250 | 6 top[3] 记录每个array当前的位置，初始-1
取三个array top[]位置后最小的下一个为next，update相应的top[], 找出三个array
在top位置的最大最小，如果差值比min_cost小（top指向-1时差值为无穷大），
更新min_cost, repeat |
|
