LeetCode Reservoir Sampling類(382 298) 題解

382：Linked List Random Node

兩種解法：

一種借鑒了洗牌算法的思想，即随機找出自己和之後一個位置，和自己互換。在構造函數裡擷取連結清單長度，複雜度O(n)。然後getRandom裡擷取[0, n-1)的随機數，找到該位置的值，複雜度期望O(n/2)。送出後Runtime 64ms。

class Solution {
private:
    ListNode* listHead;
    int listLength;
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) {
        listHead = head;
        listLength = 0;
        while (head != NULL) {
            listLength++;
            head = head->next;
        }
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        ListNode* p = listHead;
        int index = rand() % listLength;
        while (index) {
            p = p->next;
            index--;
        }
        return p->val;
    }
};
           

另一種借鑒了R算法的思想，即每次随機自己和之前的一個位置，如果在所求區間内，則互換。構造函數隻要儲存連結清單頭，複雜度O(1)。getRandom函數每個節點周遊一遍，擷取一個[0, i]的随機數(i假設為節點下标），如果是0則指派給res，複雜度為O(n)。送出後Runtime 43ms。

class Solution {
private:
    ListNode* listHead;
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) {
        listHead = head;
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        ListNode* p = listHead;
        int index = 0, pos = 0, res = 0;
        while (p != NULL) {
            index++;
            pos = rand() % index;
            if (!pos)
                res = p->val;
            p = p->next;
        }
        return res;
    }
};
           

398. Random Pick Index

這道題裡說了不要用額外空間，是以洗牌算法用不了，原因是下标是不連續的，想要從m個下标中随機抽取，前提是把m個下标都存下來。是以隻能用水塘抽樣的R算法了。

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

在水塘抽樣的wikipedia頁面，介紹了其他抽樣算法，包括：

    Reservoir with Random Sort算法：給每個元素賦上随機值，用堆儲存擁有最小/大随機值的k個元素，這樣最壞情況複雜度為O(nlogk)，即每次都要入堆。

    Weighted Random Sampling using Reservoir算法：帶權值的水塘抽樣，有兩種實作。

    Distributed Reservoir Sampling：分布式抽樣算法