j******4
发帖数: 116 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: jh170494 (jhunter), 信区: Programming
标 题: please help 这个题
关键字: algorithm
发信站: BBS 未名空间站 (Tue Jul 13 15:29:43 2010, 美东)
小弟愚鲁，这个题有人讨论过几次拉。但是还是没看明白。请各位大大不苟赐教。
题目是说，给一组词，比如‘APPLE NEWTON SCIENCE'和他们在一篇文章里出现的位置
。要求给出三个词都有的最小的RANGE。
比如：
APPLE：25 103 699 2839
NEWTON：１ ６ 16 255 645 19892
SCIENCE : 2 345 2345
说起来应该是扫描一遍就好， 可是还是没想清楚为什么这样会ＷＯＲＫ。。。
多谢。 | I**A
发帖数: 2345 | 2 能否提供以前讨论过的link? 多谢～～
【在 j******4 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: jh170494 (jhunter), 信区: Programming
: 标 题: please help 这个题
: 关键字: algorithm
: 发信站: BBS 未名空间站 (Tue Jul 13 15:29:43 2010, 美东)
: 小弟愚鲁，这个题有人讨论过几次拉。但是还是没看明白。请各位大大不苟赐教。
: 题目是说，给一组词，比如‘APPLE NEWTON SCIENCE'和他们在一篇文章里出现的位置
: 。要求给出三个词都有的最小的RANGE。
: 比如：
: APPLE：25 103 699 2839
| f**********w
发帖数: 93 | 3 我的想法是这样的，假设我们已经有了3个array a,b,c,分别代表三个单词在文章中的
位置，注意这三个数组应该是已经排序的，比较a[0], b[0], c[0],找到最大值，假设
是a[0],然后在其他的两个数组里做binary search,记录当前的最小范围，然后对a 循
环，每次都对b,c做binary search,并更新最小范围。效率应该是O(nlogn).也许有线性
的解法，我没想到 | i**r
发帖数: 40 | | s***e
发帖数: 793 | 5 从左到右扫描一边，记录当前最后出现的三个词的位置。保持一个MIN
【在 j******4 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: jh170494 (jhunter), 信区: Programming
: 标 题: please help 这个题
: 关键字: algorithm
: 发信站: BBS 未名空间站 (Tue Jul 13 15:29:43 2010, 美东)
: 小弟愚鲁，这个题有人讨论过几次拉。但是还是没看明白。请各位大大不苟赐教。
: 题目是说，给一组词，比如‘APPLE NEWTON SCIENCE'和他们在一篇文章里出现的位置
: 。要求给出三个词都有的最小的RANGE。
: 比如：
: APPLE：25 103 699 2839
| I**A
发帖数: 2345 | 6 http://www.mitbbs.com/article_t1/JobHunting/31561643_0_1.html
看haha的solution
【在 j******4 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: jh170494 (jhunter), 信区: Programming
: 标 题: please help 这个题
: 关键字: algorithm
: 发信站: BBS 未名空间站 (Tue Jul 13 15:29:43 2010, 美东)
: 小弟愚鲁，这个题有人讨论过几次拉。但是还是没看明白。请各位大大不苟赐教。
: 题目是说，给一组词，比如‘APPLE NEWTON SCIENCE'和他们在一篇文章里出现的位置
: 。要求给出三个词都有的最小的RANGE。
: 比如：
: APPLE：25 103 699 2839
|
|
