水塘抽样是动态等概率抽样。用来从一集合中随机且等概率地抽取K个元素。
- Leetcode 382
给你一个未知长度的链表,请你设计一个算法,只能遍历一次,随机地返回链表中的一个节点。
int getRandom(ListNode* head){
int ret=0;
ListNode* cur=head;
int i=1;
while(cur!=nullptr){
if(rand()%i==0){
ret=cur->val;
}
i++;
cur=cur->next;
}
return ret;
}
- Leetcode 392
给定一个可能含有重复元素的整数数组,要求随机输出一个给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
int[] nums = new int[] {1,2,3,3,3}; Solution solution = new Solution(nums);
// pick(3) 应该返回索引 2,3 或 4。每个索引的返回概率应该相等。
solution.pick(3);
// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);
#include<utility>
class Solution {
public:
vector<int> arr;
Solution(vector<int>& nums) {
arr=std::move(nums);
}
int pick(int target) {
int ret=0;
int count=0;
for(int i=0;i<arr.size();++i){
if(arr[i]==target){
count++;
if(rand()%count==0){
ret=i;
}
}
}
return ret;
}
};
- 在N个数的数组中等概率地随机选取K个数(抽奖问题)
这里的时间复杂度是O(N),即从30W的人中抽10W人仍需进行30W次的计算。vector<int> getRandom(vector<int>& arr, int k){
vector<int> ret;
for(int i=0;i<k;++i){
ret.emplace_back(arr[i]);
}
for(int i=k;i<arr.size();++i){
int j=rand()%i;
if(j<k){
ret[j]=arr[i];
}
}
return ret;
}
有没有更低时间复杂度的策略?有的,下面的抽奖方式就是:
这种抽奖方式的时间复杂度是O(k),但是拥有更高的空间复杂度,空间复杂度为O(N).vector<int> getRandom(vector<int> arr, int k){
vector<int> ret;
int size=arr.size();
for(int i=0;i<k;++i){
int randInx=rand()%(size-i)+i;
swap(arr[randInx],arr[i]);
}
for(int i=0;i<k;++i){
ret.emplace_back(arr[i]);
}
return ret;
}