LeetCode 蓄水池抽样

• 链接：https://leetcode-cn.com/tag/reservoir-sampling/
• 来源：力扣（LeetCode）
• 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

398. 随机数索引

问题描述
给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意：数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

问题分析
由于数组中所有元素都有可能是同一个元素，所以肯定不能把指定数字取出后再随机选择一个。
所以我们需要在遍历的过程中决定是否要返回某个元素返回。

• 当遍历到第 k 个指定元素，那么我们留下他的概率应该是 1/k。
• 对于前 k-1 个元素，每个元素留下的概率都是 1/(k-1)，所以前 k-1 个元素留下的概率是 $\frac{1}{k?1}?(1?\frac{1}{k})=\frac{1}{k}$，即前 k 个元素都以 1/k 的概率被留下。
• 由归纳法不难知道，这样操作就可以让每个元素最终都以等概率被保留下来。

class Solution {
    vector<int> &nums;default_random_engine e;
public:Solution(vector<int>& _nums):nums(_nums) {
    }int pick(int target) {
    int cnt = 0, last = 0;for(int i = 0; i < nums.size(); ++i)if(nums[i] == target){
    if(cnt == 0 || (e() % (cnt + 1)) >= cnt)last = i;cnt++;}return last;}
};/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(nums);* int param_1 = obj->pick(target);*/

382. 链表随机节点

这题和上一题一样，只不过是从全部元素中随机返回一个。

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
    ListNode *head;default_random_engine e;
public:/** @param head The linked list's head.Note that the head is guaranteed to be not null, so it contains at least one node. */Solution(ListNode* head): head(head){
    }/** Returns a random node's value. */int getRandom() {
    int res, cnt = 0;ListNode *ptr = head;while(ptr != nullptr){
    if(cnt == 0 || (e() % (cnt + 1)) >= cnt)res = ptr->val;cnt++;ptr = ptr->next;}return res;}
};/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(head);* int param_1 = obj->getRandom();*/