LeetCode Reservoir Sampling类(382 298) 题解

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：分布式抽样算法