M*********n
发帖数: 4839 | 1 板上兄弟贴出来过，大概是这样的，
用一个随机数generateor产生另一个随机数，基本思想是reject sampling， 但reject
的概率太大，要找更有效的方法。 |
e***s
发帖数: 799 | 2 把能accept的数放到一个数组里面，random这个数组的index。 |
M*********n
发帖数: 4839 | 3 有链接吗？就是前几天的帖子。
【在 e***s 的大作中提到】
: 把能accept的数放到一个数组里面，random这个数组的index。
|
e***s
发帖数: 799 | 4 忘了，但是我自己reword了一下写到笔记里了
Given Rand(int n), return a random number from 0 ~ n
Now design a Rand(int n, int[] except) which output number should not in
except array |
C***U
发帖数: 2406 | 5 假设except有k个数
那么就是把0~n - except影射到0~(n-k)
中间只要用到binary search 所以应该时间上还算可以把？
【在 e***s 的大作中提到】
: 忘了，但是我自己reword了一下写到笔记里了
: Given Rand(int n), return a random number from 0 ~ n
: Now design a Rand(int n, int[] except) which output number should not in
: except array
|
M*********n
发帖数: 4839 | 6 对，就是这个，问题是except太大了怎么办？比如n是1000，excep里面有980个数。
【在 e***s 的大作中提到】
: 忘了，但是我自己reword了一下写到笔记里了
: Given Rand(int n), return a random number from 0 ~ n
: Now design a Rand(int n, int[] except) which output number should not in
: except array
|
e***s
发帖数: 799 | 7 我不是很懂你的方法，binary search用在哪里？
我的方法是，
Sort except array O(nlogn)
create new 0 ~ (n-k) array O(n)
Get random number in new array O(1)
整个算法 O(nlogn)
【在 C***U 的大作中提到】
: 假设except有k个数
: 那么就是把0~n - except影射到0~(n-k)
: 中间只要用到binary search 所以应该时间上还算可以把？
|
h****n
发帖数: 1093 | 8 how can you get random number from the new created array with size n-k given
the n size random generator?
I don't think n mod n-k will give you uniform distribution.
我不是很懂你的方法，binary search用在哪里？我的方法是，Sort except array O(
nlogn)create new 0 ~ (n-k) array O........
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 e***s 的大作中提到】
: 我不是很懂你的方法，binary search用在哪里？
: 我的方法是，
: Sort except array O(nlogn)
: create new 0 ~ (n-k) array O(n)
: Get random number in new array O(1)
: 整个算法 O(nlogn)
|
e***s
发帖数: 799 | 9 newArray[Rand（n-k)]
given
【在 h****n 的大作中提到】
: how can you get random number from the new created array with size n-k given
: the n size random generator?
: I don't think n mod n-k will give you uniform distribution.
:
: 我不是很懂你的方法，binary search用在哪里？我的方法是，Sort except array O(
: nlogn)create new 0 ~ (n-k) array O........
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
h****n
发帖数: 1093 | 10 you are not given the rand(n-k) that is my question . Rand(n)mod n-k will
not work since the resulted distribution is not uniform
newArray[Rand（n-k)]
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 e***s 的大作中提到】
: newArray[Rand（n-k)]
:
: given
|
e***s
发帖数: 799 | 11 他给Rand(n)，n 不是应该随你输入什么吗？不是规定了一定要input的那个n啊！
【在 h****n 的大作中提到】
: you are not given the rand(n-k) that is my question . Rand(n)mod n-k will
: not work since the resulted distribution is not uniform
:
: newArray[Rand（n-k)]
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
h****n
发帖数: 1093 | 12 酱紫。。。Got it，不过你这方法需要额外空间啊
如果要求不使用额外空间怎么搞 |
h****n
发帖数: 2094 | 13 先选range再在range里面选。
reject
【在 M*********n 的大作中提到】
: 板上兄弟贴出来过，大概是这样的，
: 用一个随机数generateor产生另一个随机数，基本思想是reject sampling， 但reject
: 的概率太大，要找更有效的方法。
|
