s*f
2 楼
原题是:
Implement below function.
int getRandom(int N, int K[])
Constraints:
->K is sorted and contains elements in range [0,N)
->Output should be a random number between [0,N) excuding elements from K
->probability of generated number should be 1/(N-K.length) and not 1/N
-->int uniform(int N) is given which returns random number [0,N) with 1/N
probability for each number.
->No more than O(1) memory
->No more than O(N) time
提供的解法是：
public int randomNumber(int N, int[] K) { // K is sorted
int x = uniform(N - K.length); // 1 .. N - K.length
int last = 0 , i;
for (i = 0; i < K.length; i++) {
if (K[i] - last > x)
return x + last;
x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid
numbers
last = K[i];
}
return x + K[ K.length-1 ];
}
概率不好，请大家解释下这个算法什么意思，谢谢。
Implement below function.
int getRandom(int N, int K[])
Constraints:
->K is sorted and contains elements in range [0,N)
->Output should be a random number between [0,N) excuding elements from K
->probability of generated number should be 1/(N-K.length) and not 1/N
-->int uniform(int N) is given which returns random number [0,N) with 1/N
probability for each number.
->No more than O(1) memory
->No more than O(N) time
提供的解法是：
public int randomNumber(int N, int[] K) { // K is sorted
int x = uniform(N - K.length); // 1 .. N - K.length
int last = 0 , i;
for (i = 0; i < K.length; i++) {
if (K[i] - last > x)
return x + last;
x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid
numbers
last = K[i];
}
return x + K[ K.length-1 ];
}
概率不好，请大家解释下这个算法什么意思，谢谢。
u*n
3 楼
summer的活动
24 nights才给71K
只有第一个好点
7,000 BONUS POINTS
When you stay your first night by May 31, 2016
24 nights才给71K
只有第一个好点
7,000 BONUS POINTS
When you stay your first night by May 31, 2016
l*n
4 楼
天哪，我简直要疯了，我的儿子最近不知道受什么刺激了，他告诉我自己想变性。他想
当个女孩，作为母亲我听到之后肯定很生气，我觉得他脑子有病，好端端的变什么性，
而且这样会让别人觉得这个孩子有点变态。
他说他就是想变成女孩，你看看那谁谁不是也变成女人了吗，还给我各种举例子。你说
这不是脑子有问题是什么，人家有钱你有吗，再说了儿子是我们家唯一的一个独苗，现
在竟然要变成女孩子这不是搞笑吗？
反正我是肯定不能答应的，况且他现在还这么小知道什么是变性吗？他知道如果真的变
性了意味着什么吗，一个小屁孩整天不知道好好的学习就想这些乱七八糟的事情。他还
信誓旦旦的说这个是他的梦想，他一定要变成女孩子。我说你这就是脑子有病，还变性。
说实话我当时真的是内心的火不打一起处来啊，整天都不知道看的什么乱七八糟的东西
，我就告诉他你还是好好的学习吧，别在想着什么变性了。你们说说现在这个年龄段的
孩子是不是整天都会想一些连七八糟的事情啊。
当个女孩，作为母亲我听到之后肯定很生气，我觉得他脑子有病，好端端的变什么性，
而且这样会让别人觉得这个孩子有点变态。
他说他就是想变成女孩，你看看那谁谁不是也变成女人了吗，还给我各种举例子。你说
这不是脑子有问题是什么，人家有钱你有吗，再说了儿子是我们家唯一的一个独苗，现
在竟然要变成女孩子这不是搞笑吗？
反正我是肯定不能答应的，况且他现在还这么小知道什么是变性吗？他知道如果真的变
性了意味着什么吗，一个小屁孩整天不知道好好的学习就想这些乱七八糟的事情。他还
信誓旦旦的说这个是他的梦想，他一定要变成女孩子。我说你这就是脑子有病，还变性。
说实话我当时真的是内心的火不打一起处来啊，整天都不知道看的什么乱七八糟的东西
，我就告诉他你还是好好的学习吧，别在想着什么变性了。你们说说现在这个年龄段的
孩子是不是整天都会想一些连七八糟的事情啊。
t*e
5 楼
躲学校实验室好了
冻死了
【在 a*****n 的大作中提到】
: 心疼呀，交不起电费了。
冻死了
【在 a*****n 的大作中提到】
: 心疼呀，交不起电费了。
c*e
6 楼
It is filled all empty slot with n - k
for example
k = {0, 2, 5} n = 6
Uniform(30 generate random 0 - 3 and mapped to the empty slot as 1, 3, 4 .
for example
k = {0, 2, 5} n = 6
Uniform(30 generate random 0 - 3 and mapped to the empty slot as 1, 3, 4 .
y*i
7 楼
received a mail offer -
spend $4,000 earn 4,000 points
hehe
【在 u***n 的大作中提到】
: summer的活动
: 24 nights才给71K
: 只有第一个好点
: 7,000 BONUS POINTS
: When you stay your first night by May 31, 2016
spend $4,000 earn 4,000 points
hehe
【在 u***n 的大作中提到】
: summer的活动
: 24 nights才给71K
: 只有第一个好点
: 7,000 BONUS POINTS
: When you stay your first night by May 31, 2016
g*i
8 楼
可以卖身换电费
【在 a*****n 的大作中提到】
: 心疼呀，交不起电费了。
【在 a*****n 的大作中提到】
: 心疼呀，交不起电费了。
e*3
9 楼
说到底这个算法就是迅速根据Uniform（N-K.length）的结果r，找到第r个不在K内部，
但是小于N的数字，最原始的版本是O（N－K.length)复杂度，就是按照顺序在N－K这个
集合里面找对应的数字，但是这样效率太低。
底下的程序就是每个K内部的元素为跳板迅速向前跳跃找到下一个对应的数字，这句话
是精髓：
x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid numbers
注意这个－1很关键，没有－1的话x + K[ K.length-1]就会是K里面的数字，有了－1的
话，每遇到K里面的一个数字，x + K[ K.length-1]会加1。
【在 s***f 的大作中提到】
: 原题是:
: Implement below function.
: int getRandom(int N, int K[])
: Constraints:
: ->K is sorted and contains elements in range [0,N)
: ->Output should be a random number between [0,N) excuding elements from K
: ->probability of generated number should be 1/(N-K.length) and not 1/N
: -->int uniform(int N) is given which returns random number [0,N) with 1/N
: probability for each number.
: ->No more than O(1) memory
但是小于N的数字，最原始的版本是O（N－K.length)复杂度，就是按照顺序在N－K这个
集合里面找对应的数字，但是这样效率太低。
底下的程序就是每个K内部的元素为跳板迅速向前跳跃找到下一个对应的数字，这句话
是精髓：
x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid numbers
注意这个－1很关键，没有－1的话x + K[ K.length-1]就会是K里面的数字，有了－1的
话，每遇到K里面的一个数字，x + K[ K.length-1]会加1。
【在 s***f 的大作中提到】
: 原题是:
: Implement below function.
: int getRandom(int N, int K[])
: Constraints:
: ->K is sorted and contains elements in range [0,N)
: ->Output should be a random number between [0,N) excuding elements from K
: ->probability of generated number should be 1/(N-K.length) and not 1/N
: -->int uniform(int N) is given which returns random number [0,N) with 1/N
: probability for each number.
: ->No more than O(1) memory
x*i
10 楼
我也是，我看了3遍，确定不是40000。当时我也是hehe
【在 y****i 的大作中提到】
: received a mail offer -
: spend $4,000 earn 4,000 points
: hehe
【在 y****i 的大作中提到】
: received a mail offer -
: spend $4,000 earn 4,000 points
: hehe
a*n
11 楼
101.5度，靠，根本不敢出门
【在 t*****e 的大作中提到】
: 躲学校实验室好了
: 冻死了
【在 t*****e 的大作中提到】
: 躲学校实验室好了
: 冻死了
h*6
12 楼
用O(N-k.length)的空间建一个对应表，然后每次查表就可以了。
w*1
13 楼
cash + points 能算一个night吗？
【在 u***n 的大作中提到】
: summer的活动
: 24 nights才给71K
: 只有第一个好点
: 7,000 BONUS POINTS
: When you stay your first night by May 31, 2016
【在 u***n 的大作中提到】
: summer的活动
: 24 nights才给71K
: 只有第一个好点
: 7,000 BONUS POINTS
: When you stay your first night by May 31, 2016
J*n
14 楼
你在vegas?
【在 a*****n 的大作中提到】
: 101.5度，靠，根本不敢出门
【在 a*****n 的大作中提到】
: 101.5度，靠，根本不敢出门
l*8
15 楼
现在还是O（N－K.length)复杂度啊。
可以用O(log K.length)来做吧。
【在 e********3 的大作中提到】
: 说到底这个算法就是迅速根据Uniform（N-K.length）的结果r，找到第r个不在K内部，
: 但是小于N的数字，最原始的版本是O（N－K.length)复杂度，就是按照顺序在N－K这个
: 集合里面找对应的数字，但是这样效率太低。
: 底下的程序就是每个K内部的元素为跳板迅速向前跳跃找到下一个对应的数字，这句话
: 是精髓：
: x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid numbers
: 注意这个－1很关键，没有－1的话x + K[ K.length-1]就会是K里面的数字，有了－1的
: 话，每遇到K里面的一个数字，x + K[ K.length-1]会加1。
可以用O(log K.length)来做吧。
【在 e********3 的大作中提到】
: 说到底这个算法就是迅速根据Uniform（N-K.length）的结果r，找到第r个不在K内部，
: 但是小于N的数字，最原始的版本是O（N－K.length)复杂度，就是按照顺序在N－K这个
: 集合里面找对应的数字，但是这样效率太低。
: 底下的程序就是每个K内部的元素为跳板迅速向前跳跃找到下一个对应的数字，这句话
: 是精髓：
: x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid numbers
: 注意这个－1很关键，没有－1的话x + K[ K.length-1]就会是K里面的数字，有了－1的
: 话，每遇到K里面的一个数字，x + K[ K.length-1]会加1。
u*n
16 楼
I don't think so
【在 w*****1 的大作中提到】
: cash + points 能算一个night吗？
【在 w*****1 的大作中提到】
: cash + points 能算一个night吗？
a*n
17 楼
不是，在一个鸟不拉S的地方。
【在 J****n 的大作中提到】
: 你在vegas?
【在 J****n 的大作中提到】
: 你在vegas?
h*6
18 楼
我提的方法是O(1)啊，只要不限内存，想多快都可以啊。
x*n
19 楼
IHG点太泛滥了，来源太多，而且容易刷房搞活动，还有bug乱搞。
hyatt点贵因为来源少，开卡不送点，攒点慢，住的店都高级。
【在 u***n 的大作中提到】
: summer的活动
: 24 nights才给71K
: 只有第一个好点
: 7,000 BONUS POINTS
: When you stay your first night by May 31, 2016
hyatt点贵因为来源少，开卡不送点，攒点慢，住的店都高级。
【在 u***n 的大作中提到】
: summer的活动
: 24 nights才给71K
: 只有第一个好点
: 7,000 BONUS POINTS
: When you stay your first night by May 31, 2016
J*n
20 楼
100多度
鸟飞过去就晒焦了
当然鸟不拉屎的地方
【在 a*****n 的大作中提到】
: 不是，在一个鸟不拉S的地方。
鸟飞过去就晒焦了
当然鸟不拉屎的地方
【在 a*****n 的大作中提到】
: 不是，在一个鸟不拉S的地方。
l*8
21 楼
恩，O(N)内存的话，是可以O(1)时间
我前面说的是， 如果限定O(1) extra 存储的话， 可以有O(log K.length) 时间的算
法。
【在 h**6 的大作中提到】
: 我提的方法是O(1)啊，只要不限内存，想多快都可以啊。
我前面说的是， 如果限定O(1) extra 存储的话， 可以有O(log K.length) 时间的算
法。
【在 h**6 的大作中提到】
: 我提的方法是O(1)啊，只要不限内存，想多快都可以啊。
B*5
22 楼
每个人的offer好像不一样，我第一晚只有5,000，总共25晚给7万
【在 u***n 的大作中提到】
: summer的活动
: 24 nights才给71K
: 只有第一个好点
: 7,000 BONUS POINTS
: When you stay your first night by May 31, 2016
【在 u***n 的大作中提到】
: summer的活动
: 24 nights才给71K
: 只有第一个好点
: 7,000 BONUS POINTS
: When you stay your first night by May 31, 2016
D*9
23 楼
2师兄你好，我回来了
【在 t*****e 的大作中提到】
: 躲学校实验室好了
: 冻死了
【在 t*****e 的大作中提到】
: 躲学校实验室好了
: 冻死了
l*8
24 楼
O(1) space, O(log m) time, where m is the length the K array:
int randomNumber(int N, int *K, int m) {
int x = uniform(N - m);
int low = 0, up = m;
while (low < up) {
int mid = low + (up-low)/2;
if (x <= K[mid] - mid)
up = mid;
else
low = mid + 1;
}
return x + up;
}
int randomNumber(int N, int *K, int m) {
int x = uniform(N - m);
int low = 0, up = m;
while (low < up) {
int mid = low + (up-low)/2;
if (x <= K[mid] - mid)
up = mid;
else
low = mid + 1;
}
return x + up;
}
o*s
25 楼
re
【在 u***n 的大作中提到】
: summer的活动
: 24 nights才给71K
: 只有第一个好点
: 7,000 BONUS POINTS
: When you stay your first night by May 31, 2016
【在 u***n 的大作中提到】
: summer的活动
: 24 nights才给71K
: 只有第一个好点
: 7,000 BONUS POINTS
: When you stay your first night by May 31, 2016
d*r
26 楼
这里早上还得穿毛衣。
h*6
27 楼
厉害！
相关阅读
Product Recall: Adventure Playsets Bellevue Wooden Play Cen请教怀孕保险事宜PA包子有人发过关于手把手教你孩子去哈佛的帖子没有？娃忽然不肯自己睡觉了大家帮我看看如何给我儿子戒掉坏毛病，开始学说话实在忍不住了，也来说说我所认识的小黑和她的孩子...potty training听说上海的小学不教汉语拼音了农村根本没有自闭的孩子大妈们带孩子去看国庆焰火没有？请问哪里能买到一家人穿的同样款式的衣服开个贴，来问亚洲人在学校比率对孩子可能的影响娃这两天上daycare的表现还算正常吗？PA 包子---学说话的小人儿PA包子-下雨急问---雇佣这个保姆安全吗？！问个帖子大家都要求孩子必须洗脸刷牙再睡吗？看统计美国女孩高达十分之一幼年受过父亲的性侵略 (转载)