382. Linked List Random Node 蓄水池抽样法

矫情吗；* 2022-06-09 14:54 160阅读 0赞

## 382. Linked List Random Node ##

[题目链接][Link 1]

### 题意 ###

给你一个（很长）的链表，你需要从中随机地取出一个结点的值，并且保证取每个结点的概率是相同的。

### 解法 ###

[蓄水池抽样法(resevoir sampling)][resevoir sampling]的特例。

在这种情况下，蓄水池抽样法总是选择第一个对象，以1/2的概率选择第二个，以1/3的概率选择第三个，以此类推，以1/m的概率选择第m个对象。当该过程结束时，每一个对象具有相同的选中概率，即1/n，证明如下。

> 证明：第m个对象最终被选中的概率P=选择m的概率\*其后面所有对象不被选择的概率，即  
> 
> 
> P=1m×(mm\+1×m\+1m\+2×…n−1n)=1n

### 代码 ###

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    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() {
            int ans = head->val, i = 2;  
            ListNode* cur = head->next;  
            while(cur)
            {  
                int j = rand() % i;  
                if(!j)
                    ans = cur->val;  
                i++;  
                cur = cur->next;  
            }  
            return ans;  
    
        }
    private:
        ListNode* head = nullptr;
    };
    
    /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */

我还看到了一种解法

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    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):cur(head) {
        }
    
        /** Returns a random node's value. */
        int getRandom() {
            int val=cur->val;
            ListNode *temp=cur;
            for(int i=0;temp!=nullptr;temp=temp->next,++i)
            {
                uniform_int_distribution<unsigned> u(0,i);
                default_random_engine e(rand());//真正随机的种子
                unsigned int m=u(e);
                if(m<1)
                {
                    val=temp->val;
                }
            }
            return val;
        }
    private:
        ListNode *cur;
    };
    
    /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */

## 蓄水池抽样法 ##

真正的蓄水池抽样问题是，即从一个包含n个对象的列表S中随机选取k个对象，n为一个非常大或者不知道的值。通常情况下，n是一个非常大的值，大到无法一次性把所有列表S中的对象都放到内存中。

我们先把读到的前k个对象放入“水库”，对于第k+1个对象开始，以k(k\+1)的概率选择该对象，以k(k\+2)的概率选择第k+2个对象，以此类推，以km的概率选择第m个对象（m>k）。如果m被选中，则随机替换水库中的一个对象。最终每个对象被选中的概率均为kn，证明如下。

> 证明：第m个对象被选中的概率=选择m的概率*（其后元素不被选择的概率+其后元素被选择的概率*不替换第m个对象的概率），即  
> 
> 
> P=km×\[(m\+1−km\+1\+km\+1×k−1k)×(m\+2−km\+2\+km\+2×k−1k×⋯×(n−kn\+kn×k−1k)\]=km×mn=kn

#include <iostream> 
    #include <cstdlib> 
    #include <ctime> 
    #include <vector> 
    
    using namespace std;  
    
    typedef vector<int> vi;  
    typedef typename vi::iterator it;  
    typedef typename vi::const_iterator cit;  
    
    // generate a random number between i and k, 
    // both i and k are inclusive. 
    int randint(int i, int k)  
    {  
        if(i > k)  
        {  
            int t = i; i = k; k = t; // swap 
        }  
        int ret = i + rand() % (k - i + 1);  
        return ret;  
    }  
    
    // take m samples to result from input of n items. 
    bool reservoir_sampling(const vi &input, vi &result, int m)  
    {  
        srand(time(NULL));  
        if(input.size() < m)  
            return false;  
    
        result.resize(m);  
        cit it = input.begin();  
        for(int i = 0; i != m; i++)  
            result[i] = *it++;  
    
        for(int i = m; it != input.end(); i++, it++)  
        {  
            int j = randint(0, i);  
            if (j < m)  
                result[j] = *it;  
        }  
        return true;  
    }  
    
    int main()  
    {  
        const int n = 100;  
        const int m = 10;  
        vi input(n), result(m);  
    
        for(int i = 0; i < n; i++)  
            input[i] = i;  
        if(reservoir_sampling(input, result, m))  
            for (int i = 0; i < m; ++i)  
                cout << result[i] << " ";  
        cout << endl;  
        return 0;  
    }

[Link 1]: https://leetcode.com/problems/linked-list-random-node/description/
[resevoir sampling]: https://en.wikipedia.org/wiki/Reservoir_sampling