LeetCode reservoir sampling 问题总结

2017-09-29

Reservoir Sampling 即蓄水池抽样问题,具体可以参考: Reservoir sampling

在 LeetCode 上,有关 Reservoir Sampling 有两道,分别为 382. Linked List Random Node 和 398. Random Pick Index。

382. Linked List Random Node

这是 Reservoir Sampling 的基本应用,不过这里 k = 1,可以说是最简化版的:

class Solution {
private:
    ListNode* head;
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) {
        this->head=head;
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        auto h=head;
        int res=h->val;
        for(int i=2;h->next!=nullptr;i++){
            h=h->next;
            int t=rand()%i;
            if(t==0)
                res=h->val;
        }
        return res;
    }
};

398. Random Pick Index

这题类似上一题,也是 k = 1 的情况。不过这里略奇葩,不可以使用哈希表保存数字和下标,不然会爆内存;只能将 vector 保存,每次调用 pick 遍历该 vector:

class Solution {
private:
    vector<int> nums;
public:
    Solution(vector<int> nums) {
        this->nums=nums;
    }
    
    int pick(int target) {
        int res=0,n=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==target){
                if(n==0)
                    res=i,n++;
                else{
                    n++;
                    int t=rand()%n;
                    if(t==0)
                        res=i;
                }
            }
        }
        return res;
    }
};