一道的算法题（五个包子答谢） - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道的算法题（五个包子答谢）

一道的算法题（五个包子答谢）# JobHunting - 待字闺中

W*e2012-04-23 07:04

1 楼

一排符号排成环形，每种符号必须且只出现两次
比如 1231352454排成一个环形，454后面接着就是前面的123，里面每个符号都出现两次
现在计算相同符号之间的间隔，比如从1开始，找最近的另外一个1的位置，中间间隔了
2个数，结果是2
然后把两个1从环中去掉，剩下的仍然是个环，继续求2之间的间隔（不包括原来的1）
。然后反复这样操作直到环为空，求nlogn的数据结构/算法得到最后所有间隔的累加值
，例如（1的间隔+2的间隔+3的间隔+。。。）
这个问题似乎已经超出了普通的data structure求解范围

x*y2012-04-23 07:04

2 楼

I think you can use interval tree
first, break circle to list, and duplicate and append.
for each number, we have 4 as the original flatted circle duplicated,and we only care
about the distance between 1st and 2nd, also between 2nd and 3rd, which is
smaller.
second, create the interval tree according the index, the value of each node
in the tree is real distance between 2 edge leaves; wheneve a number is
kicked out, each node on the way down to it will have the value decreased by
1. In interval tree, this is log(n). Get the new distance between any 2
leaves are also log(n) in interval tree.
So, each kicking out will be log(n), for n numbers, it will be o(nlogn).