巨大的绿帽子 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

巨大的绿帽子

巨大的绿帽子# Joke - 肚皮舞运动

s*n2011-01-23 08:01

1 楼

突然想到一个题目，找到BST中离目标最近的那个数
大家又什么好解法？

D*02011-01-23 08:01

2 楼

镇上的几个主妇好不容易组织了一次不带小孩的疯狂之夜，畅饮之后两个主妇结伴走路
回家。走到一半两人都感觉到内急，恰巧边上小道是墓地，两个人拐弯进去，Shelly尿
完后脱下内裤擦干净，Jamie舍不得弄脏内裤，刚好她边上是个新墓，她借着月光解下
几个系鲜花的丝带用。
第二天是周末，Shelly的老公大早上打电话给Jamie老公，“昨晚到底发生了什么事？
我太太回家竟然裙下光着，我有很不好的感觉。。。”
“是啊，我也想问，都不大好张口，我刚才起床，看见Jamie的屁股上有个不沾胶的软
卡片，上写“消防队全体同仁敬上””

s*y2011-01-23 08:01

3 楼

I saw this question on this board 2-3 weeks ago.

【在 s******n 的大作中提到】

: 突然想到一个题目，找到BST中离目标最近的那个数
: 大家又什么好解法？

i*y2011-01-23 08:01

4 楼

尿尿为什么要擦？

g*u2011-01-23 08:01

5 楼

假设该元素不在BST中，首先找到最后一个比该元素小的节点，然后找到第一个比该元素大的节点，返回2个节点中离目标最近的节点。
下面是实现，等待拍砖。
node * findClose(node *root, int value)
{
if(!root)
return NULL;
node * smaller=findLastSmaller(root, value);
node * greater=findFirstGrearer(root, value);
//we will also need to check both of smaller and greater are not NULL
return value-smaller->value< greater->value - value?smaller:greater;
}
node * findLastSmaller(node * root, int value)
{
if(!root)
return NULL;
node * result=NULL;
while(root)
{
if(root->value >= value)
root=root->left;
else{
result=root;
root=root->right;
}
}
return result;
}
node * findFirstGreater(node * root, int value)
{
if(!root)
return NULL;
node * result=NULL;
while(root)
{
if(root->value<=value)
root=root->right;
else{
result=root;
root=root->left;
}
}
return result;
}
时间复杂度是 O(log n), 空间复杂度是O(1)
还有一个做法就是in-order visit,然后做binary search，找到该元素的区间，然后寻找目标节点。时间复杂度是一样的，但空间复杂度就是 O(n)了

【在 s******n 的大作中提到】

: 突然想到一个题目，找到BST中离目标最近的那个数
: 大家又什么好解法？