...
| 代码块 |
|---|
int getRandom(ListNode *head) {
int ans;
int i = 0;
for(auto node = head; node != nullptr; node = node->next) {
if(rand() % i == 0) { // 第i个结点选中的概率为1/i，如果命中
ans = node->val;
}
i++;
}
return ans;
} |
接下来是随机选取m个结点，算法思路如下：
- 如果接收数据量小于m，则依次放入蓄水池。
- 当接收到第i个数据，且i>=m时，在[0, i]范围内随机选取数d，如果d落在[0, m-1]范围内，则用收到的数替换蓄水池中的第d个数据。
示例代码如下：
| 代码块 |
|---|
vector<int> getRandom(ListNode *node, int m) {
vector<int> pool(m);
int i = 0;
while(i < m && node != nullptr) {
pool[i] = node->val;
node = node->next;
i++;
}
while(node != nullptr) {
int d = rand() % (i+1); // 随机获得一个[0,i]内的整数
if(d < m) { // 如果整数落在[0,m-1]范围内，则替换蓄水池中的元素
pool[d] = node->val;
}
node = node->next;
}
return pool;
} |