蓄水池抽样
n个元素,从中选m个,使得每个元素被选中的概率都是m/n,该题中,m = 1。
用一个变量r存储当前存储选择的数是多少。
-
如果只有一个元素,则一定选择该数,r = x
-
如果有两个数,换成当前数的概率为1/2
-
如果有三个数,换成当前数的概率为1/3
-
以此类推
这样,每个数被随机到的概率是一样的,且和n的大小无关。
证明:有n个数,随机到k个数的概率一定是1/n?
$ 时间复杂度O(N),空间复杂度O(1) $
参考文献
lc究极班
AC代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
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* h;
Solution(ListNode* head) {
h = head;
}
/** Returns a random node's value. */
int getRandom() {
int r = 0, n = 0 ;
for (auto p = h ; p ; p = p->next){
n ++;
if (rand() % n == 0)
r = p->val;
}
return r;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(head);
* int param_1 = obj->getRandom();
*/
佬,图片显示不出来了