LeetCode|LeetCode---蓄水池抽样算法
面试的时候被问到这个问题了，一脸懵逼。
问题：从n个元素中随机抽取k个元素，其中N无法确定。
解法：我们总是选择第一个对象，以1/2的概率选择第二个，以1/3的概率选择第三个，以此类推，以1/m的概率选择第m个对象。当该过程结束时，每一个对象具有相同的选中概率，即1/n，证明如下。
证明：第m个对象最终被选中的概率P=选择m的概率*其后面所有对象不被选择的概率，即
文章图片
对应蓄水池抽样问题，可以类似的思路解决。先把读到的前k个对象放入“水库”，对于第k+1个对象开始，以k/(k+1)的概率选择该对象，以k/(k+2)的概率选择第k+2个对象，以此类推，以k/m的概率选择第m个对象（m>k）。如果m被选中，则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n，证明如下。
证明：第m个对象被选中的概率=选择m的概率*（其后元素不被选择的概率+其后元素被选择的概率*不替换第m个对象的概率），即
文章图片
382. 链表随机节点
文章图片
/**
* 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. */
ListNode *head;
Solution(ListNode* head) {
this->head = head;
}/** Returns a random node's value. */
int getRandom() {int ans = head->val;
int i = 2;
auto node = head->next;
while(node){
int j = rand()%i;
if(j==0)ans = node->val;
++i;
node=node->next;
}
return ans;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/398. 随机数索引
文章图片
class Solution {
public:
vector a;
Solution(vector nums) {
this->a = nums;
}int pick(int target) {
int ans;
int cnt = 1;
for(int i = 0;
i 【LeetCode|LeetCode---蓄水池抽样算法】
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- LeetCode|LeetCode 876. 链表的中间结点