一. 蓄水池抽样算法
leetcode 382. 链表随机节点
题目链接
本题新奇之处在于在链表中查找随机一个数。
每次只保留一个数,当遇到第 i 个数时,以 1/i的概率保留它,(i-1)/i的概率保留原来的数。
这样每个节点概率就相等了
/**
* 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:
ListNode* h;
Solution(ListNode* head) {
h=head;
}
int getRandom() {
int n=0;
int c=-1;
for(auto p=h;p;p=p->next)
{
n++;
if(rand()%n==0)c=p->val;
}
return c;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(head);
* int param_1 = obj->getRandom();
*/
二. Fisher-Yates 洗牌算法
leetcode 384. 打乱数组
题目链接
class Solution {
public:
vector<int>nums;
Solution(vector<int>& a) {
nums=a;
}
vector<int> reset() {
return nums;
}
vector<int> shuffle() {
auto b=nums;
int n=nums.size();
for(int i=0;i<n;i++)
{
swap(b[i],b[i+rand()%(n-i)]);
}
return b;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* vector<int> param_1 = obj->reset();
* vector<int> param_2 = obj->shuffle();
*/