r*****e 发帖数: 146 | |
K*********n 发帖数: 2852 | 2 这个……如果没有其他信息只能深度优先广度优先了。就得O(n)了……
【在 r*****e 的大作中提到】 : 如何随机找二叉树中的任意节点? 谢谢!
|
g****y 发帖数: 240 | 3 是给一个值找一个节点,还是说随机返回二叉树中的一个节点?
【在 r*****e 的大作中提到】 : 如何随机找二叉树中的任意节点? 谢谢!
|
r*****e 发帖数: 146 | 4 随机返回一个树中的节点
TreeNode* get_random_node(TreeNode* root);
【在 g****y 的大作中提到】 : 是给一个值找一个节点,还是说随机返回二叉树中的一个节点?
|
b***m 发帖数: 5987 | 5 要求概率完全平均吗?时间上有要求吗?
【在 r*****e 的大作中提到】 : 随机返回一个树中的节点 : TreeNode* get_random_node(TreeNode* root);
|
g****y 发帖数: 240 | 6 那就traversal 所有的节点,然后用reservior sampling
【在 r*****e 的大作中提到】 : 随机返回一个树中的节点 : TreeNode* get_random_node(TreeNode* root);
|
r*****e 发帖数: 146 | 7 概率平均, 时间上没有
【在 b***m 的大作中提到】 : 要求概率完全平均吗?时间上有要求吗?
|
p*****2 发帖数: 21240 | 8
这样应该就可以了吧?
【在 g****y 的大作中提到】 : 那就traversal 所有的节点,然后用reservior sampling
|
b***m 发帖数: 5987 | 9
这个,可以把所有node展开存到数组里吧,然后调用随机数。这个问题问得很含糊啊!
【在 r*****e 的大作中提到】 : 概率平均, 时间上没有
|
l*****a 发帖数: 14598 | 10 放啥数组,任意order traverse,每个按照1/k的概率决定用当前还是原来的。
【在 b***m 的大作中提到】 : : 这个,可以把所有node展开存到数组里吧,然后调用随机数。这个问题问得很含糊啊!
|
|
|
b***m 发帖数: 5987 | 11
说详细些?
【在 l*****a 的大作中提到】 : 放啥数组,任意order traverse,每个按照1/k的概率决定用当前还是原来的。
|
l*****a 发帖数: 14598 | 12 k=1;
for each node
{
1/K的可能性使用当前node,
1-1/K的可能性使用上次的结果
k++;
}
【在 b***m 的大作中提到】 : : 说详细些?
|
r*****e 发帖数: 146 | 13 写了一个。弱问一句,初始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*******b 发帖数: 2586 | 14 噢,有道理呀,只要遍历树结构就无所谓了跟一个一个取是一样的
【在 l*****a 的大作中提到】 : 放啥数组,任意order traverse,每个按照1/k的概率决定用当前还是原来的。
|
b***m 发帖数: 5987 | 15
俺愚钝呀,还是没看懂。
【在 l*******b 的大作中提到】 : 噢,有道理呀,只要遍历树结构就无所谓了跟一个一个取是一样的
|
l*******b 发帖数: 2586 | 16 http://en.wikipedia.org/wiki/Reservoir_sampling
貌似就是前面说的这个reservoir sampling. 要遍历一遍整个树的
【在 b***m 的大作中提到】 : : 俺愚钝呀,还是没看懂。
|
p*****2 发帖数: 21240 | 17
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*****2 发帖数: 21240 | 18
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****x 发帖数: 2483 | 19 这题不就是做烂了的那道google的无限输入流随机取数吗 |
b***m 发帖数: 5987 | 20
我就是笨,没看懂你的思想。
【在 p*****2 的大作中提到】 : : TreeNode ans=null; : int count=0; : Random rand=new Random(); : : void getRandNode(TreeNode root) : { : if(root==null) return; : : count++;
|
|
|
l*****a 发帖数: 14598 | 21 这个写的很清楚了吧?
k=1;
for each node
{
1/K的可能性使用当前node,
1-1/K的可能性使用上次的结果
k++;
}
【在 b***m 的大作中提到】 : : 我就是笨,没看懂你的思想。
|
b***m 发帖数: 5987 | 22
不懂耶,我有够笨了吧。
【在 l*****a 的大作中提到】 : 这个写的很清楚了吧? : k=1; : for each node : { : 1/K的可能性使用当前node, : 1-1/K的可能性使用上次的结果 : k++; : }
|
l*****a 发帖数: 14598 | 23 看看http://en.wikipedia.org/wiki/Reservoir_sampling
把它跟BT traverse结合起来
【在 b***m 的大作中提到】 : : 不懂耶,我有够笨了吧。
|
b***m 发帖数: 5987 | |
b***m 发帖数: 5987 | 25
有些明白了。反正就是要把整个树都遍历一遍呗。对吧?
【在 p*****2 的大作中提到】 : : TreeNode ans=null; : int count=0; : Random rand=new Random(); : : void getRandNode(TreeNode root) : { : if(root==null) return; : : count++;
|
p*****2 发帖数: 21240 | 26
对。
【在 b***m 的大作中提到】 : : 有些明白了。反正就是要把整个树都遍历一遍呗。对吧?
|
b***m 发帖数: 5987 | 27 这个跟我想的不一样。为什么不能事先遍历一次树,把节点全部存在一个数组里,然后
随机取?否则岂不是每次都要遍历? |
p*****2 发帖数: 21240 | 28
如果树很大,你没有内存建立你的数组咋办?
【在 b***m 的大作中提到】 : 这个跟我想的不一样。为什么不能事先遍历一次树,把节点全部存在一个数组里,然后 : 随机取?否则岂不是每次都要遍历?
|
b***m 发帖数: 5987 | 29
了解。我以前的行业没有太大数据量,讲究的是空间换时间。所有常用的浮点数运算我
们都做成大表一次性load到内存里,需要计算的时候到表里查。
【在 p*****2 的大作中提到】 : : 如果树很大,你没有内存建立你的数组咋办?
|
Y********f 发帖数: 410 | 30 这个最好是能在节点中存子树的节点数吧,如果是平衡树的话随机查找/插入/删除都是
logN
【在 r*****e 的大作中提到】 : 如何随机找二叉树中的任意节点? 谢谢!
|
|
|
d*********g 发帖数: 154 | 31 练习一个
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;
}
}
} |