fucking-algorithm
fucking-algorithm copied to clipboard
如何在无限序列中随机抽取元素 :: labuladong的算法小抄
请问下思考2 randomGet 有文章吗
参考382. 链表随机节点和东哥的思路,写了下398. 随机数索引的java代码
思路还是和前一个题一样,因为数组可能很大,我们就把nums[k] == target的每一个当做链表的节点即可,而下标就是val
class Solution {
int[] nums;
Random r = new Random();
public Solution(int[] nums) {
this.nums = nums;
}
public int pick(int target) {
int i = 0, res = 0;
for (int k = 0; k < nums.length; k++) {
if (nums[k] == target) {
i++;
if (0 == r.nextInt(i)) {
res = k;
}
}
}
return res;
}
}
有点疑惑的是,对于使用nextInt(i)在遍历一遍的情况下随机选取数据这个过程,是如何保证一定能满足if语句的呢(即如何保证一定可以获得一个答案值)?为什么不会出现遍历一遍res没有被赋值的情况
这个问题的难点在于,随机选择是「动态」的,比如说你现在你有 5 个元素,你已经随机选取了其中的某个元素 a 作为结果,但是现在再给你一个新元素 b,你应该留着 a 还是将 b 作为结果呢,以什么逻辑选择 a 和 b 呢?
这个问题,本文感觉还是没解释清楚哇?为什么要选择b呢?
有点疑惑的是,对于使用nextInt(i)在遍历一遍的情况下随机选取数据这个过程,是如何保证一定能满足if语句的呢(即如何保证一定可以获得一个答案值)?为什么不会出现遍历一遍res没有被赋值的情况
我也有同样的疑惑:如何保证一定可以获得一个答案值?为什么不会出现遍历一遍res没有被赋值的情况?
@victory460 @zyxing-Andrew 在循环第一次执行的时候,randInt(1)
生成的数一定是 0,所以相当于 res
被初始化为 0 了。
这道题目我觉得困惑的点在于,为什么不被替换的概率是 1-1/(i+1);其实可以这样想,保持原来的选择,这个选择的是哪个我们不清楚,但是从概率学上说应该是有i种可能,每种可能的概率为1/(i+1),所以得到:i/(i+1)。
东哥,在随机抽取k个元素时,在程序里能不能初始化 int i=k -1 ; // 生成一个 [0, i) 之间的整数 int j = r.nextInt(++i); 这样第一次选中的概率就为1
如果不可以,那么是不是意味着解决只抽取一个元素的问题, 需要初始化 int i=1;
理解了,但是写到力扣上不对是怎么回事
少了一个this,可以这样理解,第一题前i-1个元素爱咋更新咋更新res,但是第i个元素把res定死之后,从i+1一直到n都处于不更新res的概率,把它们相乘就是证明的那个图
写了个C++版本的,力扣居然超时了,没搞懂为啥会超时
class Solution {
vector<int> nums;
public:
Solution(vector<int>& nums) {
this->nums.assign(nums.begin(), nums.end());
}
int pick(int target) {
int counter = 0;
int res = -1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != target) continue;
counter++;
if (rand() % counter == 0) res = i;
}
return res;
}
};