松鼠吃的那种坚果能吃吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>pets - 心有所宠

松鼠吃的那种坚果能吃吗？

松鼠吃的那种坚果能吃吗？# pets - 心有所宠

r*e2011-10-23 07:10

1 楼

如何随机找二叉树中的任意节点？谢谢！

B*u2011-10-23 07:10

2 楼

核心提示:美国《外交政策》预测2025年时，99座新城市有望跻身全世界最大600座城市
行列，其中72座来自中国。
由于欧美增长势头脆弱，世界经济均势正通过城市化进程以前所未有的速度和规模
由西方向东方转移。2025年最具活力城市排名榜出炉，其中40%的城市同属一个国家—
——中国。
从福州到武汉，许多是你闻所未闻的城市，但它们都是中国将引导21世纪城市革命
的见证。尽管到2025年时西方并未完全黯然失色———13座美国城市和仅3座欧洲城市
入围，但太阳的确正在西沉。

p*m2011-10-23 07:10

3 楼

树上掉下来那种坚果，总看松鼠在吃，不知道能不能吃啊

K*n2011-10-23 07:10

4 楼

这个……如果没有其他信息只能深度优先广度优先了。就得O(n)了……

【在 r*****e 的大作中提到】

: 如何随机找二叉树中的任意节点？谢谢！

r*32011-10-23 07:10

5 楼

我朝人口基数在那，不管干啥必须是规模第一的，春游人口流动也好农村人口城市化也好

l*t2011-10-23 07:10

6 楼

你可以尝尝，我尝过，味道有点苦

g*y2011-10-23 07:10

7 楼

是给一个值找一个节点，还是说随机返回二叉树中的一个节点？

【在 r*****e 的大作中提到】

: 如何随机找二叉树中的任意节点？谢谢！

G*e2011-10-23 07:10

8 楼

我也就觉得我自己比较奇怪去尝那个，没想到还有别人也好奇这个。。。。
苦的。。。不好吃。至少咱跟松鼠的品位不同。。。

r*e2011-10-23 07:10

9 楼

随机返回一个树中的节点
TreeNode* get_random_node(TreeNode* root);

【在 g****y 的大作中提到】

: 是给一个值找一个节点，还是说随机返回二叉树中的一个节点？

i*i2011-10-23 07:10

10 楼

橡子，涩的一塌糊涂

【在 p******m 的大作中提到】

: 树上掉下来那种坚果，总看松鼠在吃，不知道能不能吃啊

b*m2011-10-23 07:10

11 楼

要求概率完全平均吗？时间上有要求吗？

【在 r*****e 的大作中提到】

: 随机返回一个树中的节点
: TreeNode* get_random_node(TreeNode* root);

f*n2011-10-23 07:10

12 楼

恩，我以前被松鼠掉下来的核桃砸过，然后就很开心的每到季节就去捡核桃了~比超市
卖的小，但是香很多，甜而且不涩

g*y2011-10-23 07:10

13 楼

那就traversal 所有的节点，然后用reservior sampling

【在 r*****e 的大作中提到】

: 随机返回一个树中的节点
: TreeNode* get_random_node(TreeNode* root);

a*e2011-10-23 07:10

14 楼

品味独特的是大有人在啊：）有没有就好这口的。

【在 G********e 的大作中提到】

: 我也就觉得我自己比较奇怪去尝那个，没想到还有别人也好奇这个。。。。
: 苦的。。。不好吃。至少咱跟松鼠的品位不同。。。

r*e2011-10-23 07:10

15 楼

概率平均, 时间上没有

【在 b***m 的大作中提到】

: 要求概率完全平均吗？时间上有要求吗？

c*32011-10-23 07:10

16 楼

想当年我们的祖先还在和他们抢着吃呢嘿嘿嘿。。。。：）

p*22011-10-23 07:10

17 楼

这样应该就可以了吧？

【在 g****y 的大作中提到】

: 那就traversal 所有的节点，然后用reservior sampling

d*a2011-10-23 07:10

18 楼

咱挖坑必须专业，啥叫坚果啊，有个名没有，没名也得有图啊。

b*m2011-10-23 07:10

19 楼

这个，可以把所有node展开存到数组里吧，然后调用随机数。这个问题问得很含糊啊！

【在 r*****e 的大作中提到】

: 概率平均, 时间上没有

l*a2011-10-23 07:10

20 楼

放啥数组，任意order traverse,每个按照1/k的概率决定用当前还是原来的。

【在 b***m 的大作中提到】

:
: 这个，可以把所有node展开存到数组里吧，然后调用随机数。这个问题问得很含糊啊！

b*m2011-10-23 07:10

21 楼

说详细些？

【在 l*****a 的大作中提到】

: 放啥数组，任意order traverse,每个按照1/k的概率决定用当前还是原来的。

l*a2011-10-23 07:10

22 楼

k=1;
for each node
{
1/K的可能性使用当前node,
1-1/K的可能性使用上次的结果
k++;
}

【在 b***m 的大作中提到】

:
: 说详细些？

r*e2011-10-23 07:10

23 楼

写了一个。弱问一句，初始ret的时候有些糊涂。一定要遍历的第一个？
TreeNode* get_random_node(TreeNode* root){
srand(time(NULL));
InOrderNextIterator it(root);
int cnt = 0;
int j = 0;
TreeNode* ret = root;//or一定要遍历的第一个？也就是in-order的最小？
TreeNode* cur = NULL;
while(it.has_next()){
cur = it.next();
cnt++;
j = rand()%cnt;
if(0 == j)
ret = cur;
}
return ret;
}

l*b2011-10-23 07:10

24 楼

噢，有道理呀，只要遍历树结构就无所谓了跟一个一个取是一样的

【在 l*****a 的大作中提到】

: 放啥数组，任意order traverse,每个按照1/k的概率决定用当前还是原来的。

b*m2011-10-23 07:10

25 楼

俺愚钝呀，还是没看懂。

【在 l*******b 的大作中提到】

: 噢，有道理呀，只要遍历树结构就无所谓了跟一个一个取是一样的

l*b2011-10-23 07:10

26 楼

http://en.wikipedia.org/wiki/Reservoir_sampling
貌似就是前面说的这个reservoir sampling. 要遍历一遍整个树的

【在 b***m 的大作中提到】

:
: 俺愚钝呀，还是没看懂。

p*22011-10-23 07:10

27 楼

InOrderNextIterator it(root);
你这是什么东西呢？

【在 r*****e 的大作中提到】

: 写了一个。弱问一句，初始ret的时候有些糊涂。一定要遍历的第一个？
: TreeNode* get_random_node(TreeNode* root){
: srand(time(NULL));
: InOrderNextIterator it(root);
: int cnt = 0;
: int j = 0;
: TreeNode* ret = root;//or一定要遍历的第一个？也就是in-order的最小？
: TreeNode* cur = NULL;
: while(it.has_next()){
: cur = it.next();

p*22011-10-23 07:10

28 楼

TreeNode ans=null;
int count=0;
Random rand=new Random();

void getRandNode(TreeNode root)
{
if(root==null) return;

count++;
if(rand.nextInt(count)==0)
ans=root;
getRandNode(root.left);
getRandNode(root.right);

}

【在 b***m 的大作中提到】

:
: 俺愚钝呀，还是没看懂。

w*x2011-10-23 07:10

29 楼

这题不就是做烂了的那道google的无限输入流随机取数吗

b*m2011-10-23 07:10

30 楼

我就是笨，没看懂你的思想。

【在 p*****2 的大作中提到】

:
: TreeNode ans=null;
: int count=0;
: Random rand=new Random();
:
: void getRandNode(TreeNode root)
: {
: if(root==null) return;
:
: count++;

l*a2011-10-23 07:10

31 楼

这个写的很清楚了吧？
k=1;
for each node
{
1/K的可能性使用当前node,
1-1/K的可能性使用上次的结果
k++;
}

【在 b***m 的大作中提到】

:
: 我就是笨，没看懂你的思想。

b*m2011-10-23 07:10

32 楼

不懂耶，我有够笨了吧。

【在 l*****a 的大作中提到】

: 这个写的很清楚了吧？
: k=1;
: for each node
: {
: 1/K的可能性使用当前node,
: 1-1/K的可能性使用上次的结果
: k++;
: }

l*a2011-10-23 07:10

33 楼

看看http://en.wikipedia.org/wiki/Reservoir_sampling
把它跟BT traverse结合起来

【在 b***m 的大作中提到】

:
: 不懂耶，我有够笨了吧。

b*m2011-10-23 07:10

34 楼

能不能把你的思想写成函数？

b*m2011-10-23 07:10

35 楼

有些明白了。反正就是要把整个树都遍历一遍呗。对吧？

【在 p*****2 的大作中提到】

:
: TreeNode ans=null;
: int count=0;
: Random rand=new Random();
:
: void getRandNode(TreeNode root)
: {
: if(root==null) return;
:
: count++;

p*22011-10-23 07:10

36 楼

对。

【在 b***m 的大作中提到】

:
: 有些明白了。反正就是要把整个树都遍历一遍呗。对吧？

b*m2011-10-23 07:10

37 楼

这个跟我想的不一样。为什么不能事先遍历一次树，把节点全部存在一个数组里，然后
随机取？否则岂不是每次都要遍历？

p*22011-10-23 07:10

38 楼

如果树很大，你没有内存建立你的数组咋办？

【在 b***m 的大作中提到】

: 这个跟我想的不一样。为什么不能事先遍历一次树，把节点全部存在一个数组里，然后
: 随机取？否则岂不是每次都要遍历？

b*m2011-10-23 07:10

39 楼

了解。我以前的行业没有太大数据量，讲究的是空间换时间。所有常用的浮点数运算我
们都做成大表一次性load到内存里，需要计算的时候到表里查。

【在 p*****2 的大作中提到】

:
: 如果树很大，你没有内存建立你的数组咋办？

Y*f2011-10-23 07:10

40 楼

这个最好是能在节点中存子树的节点数吧，如果是平衡树的话随机查找/插入/删除都是
logN

【在 r*****e 的大作中提到】

: 如何随机找二叉树中的任意节点？谢谢！

d*g2011-10-23 07:10

41 楼

练习一个
class RandomNodeGetterInBinaryTree
{
private static int totalNumNodesSoFar = 0;
private static TreeNode result = new TreeNode();

public TreeNode GetRandomNodeInBinaryTree(TreeNode root)
{
PreOrderTraverse(root);
return result;
}

private void PreOrderTraverse(TreeNode node)
{
if(node == null) return;

ReservoirSampling(node);
PreOrderTraverse(node.left);
PreOrderTraverse(node.right);
}

private void ReservoirSampling(TreeNode node)
{
++totalNumNodesSoFar;
Random random = new Random();
int j = random.nextInt(totalNumNodesSoFar)+1;
if(j <= 1)
{
result = node;
}
}
}