0%

Reservoir sampling-Algorithem R

Algorithm R

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
//
// Algorithm R
//
#include <yong/head.h>

// rand [low, high)
int Rand(int low, int high);

class Solution {
public:
vector<int> func(vector<int>& vec, int k) {
vector<int> ret(k);
// fill reservior array
for (int i = 0; i < k; i++)
ret[i] = vec[i];

// replace element with gradually decreasing probability
for (int i = k, n = vec.size(); i < n; i++) {
int val = Rand(0, i);
if (val < k) {
ret[val] = vec[i];
}
}
return ret;
}
};