fb店面sign

我觉得这道题就是reservoir sampling  可以先把matrix转化为长 N*M的1d array ，然后在这个1d的array里选k个点，这就变成了经典题：http://www.geeksforgeeks.org/reservoir-sampling/， 然后把选出的1d index转化matrix col and row index  

同意吗？

francisliu 发表于 2016-10-5 12:58
我本来就是来扯淡的，为什么不是呢？
K个随机的位置，均匀分布即可。

不是很懂...比如说有1 2 3 4 5 6 7 8 9.......K=3    假设你取3...那你如何找 剩下的2个呢?

waikai 发表于 2016-10-5 13:00
额，或许我没解释清楚？ 不是每个取值都是unique的就是随意random的问题。比如极端的情况。100个里面选10 ...

哦懂了..所以是不是这个呀
http://www.geeksforgeeks.org/reservoir-sampling/

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

emmonenirvana 发表于 2016-10-7 10:08
楼主感觉你这个解法并不能保证每个点等概率.
比如第二个位置被取到的概率是：
k / total * ( k- 1 / to ...

你表达式错了额，最后是k/(total-1)，因为total不管自减了。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

celtspirit 发表于 2016-10-9 00:12
grid是你自己建的存储位置的么？感觉要建立一个l*w的matrix然后存储l*w个index再对index进行操作吧。空间 ...

是的，自己建立。输入是长度和宽度

是不是也需要证明每个抽取的点的概率相等且是1/(l*w)?