Fisher–Yates shuffle 洗牌算法
海量資料随機抽樣問題(蓄水池問題)
題目
class Solution {
private:
vector<int> vc;
public:
Solution(vector<int> nums) {
vc = nums;
}
int pick(int target) {
vector<int> tmp;
int size = 0;
for (int i = 0; i < vc.size(); ++i) {
if (target == vc[i]) {
if (tmp.size() != 0) {
int lim = 66666666 - 66666666 % i;
int id = rand();
while (id > lim) id = rand();
id %= ++size;
if (id == 0) tmp[id] = i;
} else {
++size;
tmp.push_back(i);
}
}
}
return tmp[0];
}
};
View Code
利用rand7生成rand10
首先這個是生成1--7的,然後也很容易 -1 生成0--6(友善我使用)
是以就是可以這樣:rand7() * 7 + rand7()
0: 0 1 2 3 4 5 6
1: 7 8 9 10 11 12 13
2: 14 15 16 17 18 19 20
3: 21 22 23 24 25 26 27
4: 28 29 30 31 32 33 34
5: 35 36 37 38 39 40 41
6: 42 43 44 45 46 47 48
可以把大于等于40的都排除,那麼就産生了6份 0---9的數字了。
class Solution {
public:
int my() {
return rand7() - 1;
}
int rand10() {
int seed = 7;
int t = my() * seed + my();
while (t > 39) t = my() * seed + my();
return t % 10 + 1;
}
};