-
Notifications
You must be signed in to change notification settings - Fork 13
/
Rand470.java
62 lines (51 loc) · 1.29 KB
/
Rand470.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package Leetcode;
import Leetcode.SolBase;
public class Rand470 extends SolBase {
/**Method1: Rejection Sampling; Time:O(1) - O(∞); Space:O(1) **/
/*
为什么? (rand7()−1)∗7+rand7()
1. 首先 rand7()-1得到的数的集合为 { 0,1,2,3,4,5,6}
2. 再乘 7 后得到的集合 A 为 { 0,7,14,21,28,35,42}
3. 后面 rand7() 得到的集合B为 { 1,2,3,4,5,6,7}
*/
public int rand10_1() {
int row, col, res;
do {
row = rand7();
col = rand7();
res = (row -1) * 7 + col;
} while(res > 40);
return (res -1) % 10 + 1;
}
/**Method2: Rejection Sampling By Use Rejection Sampling; Time:O(1) - O(∞); Space:O(1) **/
public int rand10_2() {
int row, col, res;
while(true) {
row = rand7();
col = rand7();
res = (row -1) * 7 + col;
if (res <= 40) {
return (res -1) % 10 + 1;
}
row = res - 40;
col = rand7();
// get uniform dist from 1 - 63
res = (row - 1) * 7 + col;
if (res <= 60) {
return (res -1) % 10 + 1;
}
row = res - 60;
col = rand7();
// get uniform dist from 1 - 21
res = (row - 1) * 7 + col;
if (res <= 20) {
return (res -1) % 10 + 1;
}
}
}
}
class SolBase {
int rand7() {
return 0; //TODO
};
}