# Reservoir sampling

Posted by SkyHigh on September 17, 2016

# Reservoir sampling

Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing n items, where n is either a very large or unknown number. Typically n is large enough that the list doesn’t fit into main memory.

——Wiki

• 先将第一个对象放入内存，即选中该对象
• 对每一个后面的对象i
• 有1/i的概率会用新值覆盖旧的值
• 有1-1/i的概率会丢弃新的值
• 根据上面的情况，如果总共有k个对象，那么
• 对象1会以概率 被选中
• 对象2会以概率 被选中
• 对象3会以概率 被选中

### 1.Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note: The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums is equal to 1.
solution.pick(1);


class Solution {
public:
vector<int> nums;
Solution(vector<int> nums) {
this->nums = nums;
srand(NULL);
}
int pick(int target) {
int cnt = 0;
int ind = -1;
for(int i=0;i<nums.size();i++){
if(nums[i]==target){
cnt++;
if(ind==-1)
ind = i;
else if(rand()%cnt==0)
ind = i;
}
}
return ind;
}
};
/**
\* Your Solution object will be instantiated and called as such:
\* Solution obj = new Solution(nums);
\* int param_1 = obj.pick(target);
\*/


Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();


/**
* 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 guanranteed to be not null, so it contains at least one node. */
}

/** Returns a random node's value. */
int getRandom() {
int rd = 1;
ListNode* tmp = h;
ListNode* res = NULL;
while(tmp){
if(rand()%rd==0)
res = tmp;
tmp = tmp->next;
rd++;
}
return res->val;
}
private:
ListNode* h;
};

/**
\* Your Solution object will be instantiated and called as such:
\* Solution obj = new Solution(head);
\* int param_1 = obj.getRandom();
\*/