[LeetCode] 398. Random Pick Index (Reservoir Sampl

edagarli 发布于2019-08-16 13:46 / 622人阅读

Problem

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

Solution

class Solution {
    int[] nums;
    Random random;

    public Solution(int[] nums) {
        this.random = new Random();
        this.nums = nums;
    }
    
    public int pick(int target) {
        int res = -1;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != target) continue;
            else {
                count++;
                if (random.nextInt(count) == 0) res = i;
            }
        }
        return res;
    }
}

/*
At first, let"s get clear that count is used to count the target number in nums. Say we now we have nums=[1,5,5,6,5,7,9,0] and the target is 5.

Now let"s focus on the loop. When i=1, we get the first target number, and by rnd.nextInt(++count) we select a random number between [0, 1), which means actually you could only select 0, so the probability of making result = 1 is 1.

Keep going. In the loop where i = 2, we get the second number. Now we have to get a random number in {0,1}. So what should we do if we want to keep result = 1? It"s simple: we have to make sure that, at this time, the random number generated should be 1 rather than 0 (otherwise the value of result will be changed), so the probability of keeping result = 1 is 1 * 1/2.

It is similar when we get the third target number, i.e., i = 4. Now we have to get a random number in {0,1,2}. If we still wish to keep result = 1, the only way is to randomly get number 1 or 2 rather than 0, and the probability is 2/3. So the total probability of keeping result = 1 will be 1 * 1/2 * 2/3.

Since we have four target number 5 here, the final probability of keeping result = 1 would be 1 * 1/2 * 2/3 * 3/4 = 1/4, which means the probability of picking index 0 is 1/4 as the problem required. The probability is the same if you wish to pick another index.

You may ask what is the probability of picking the last possible index 4? Well, it simpler. You may ignore all operations before the loop where i = 4, and the only thing you have to do is to get the random number 0 among {0,1,2,3} in the loop where i = 4, so the probability is exactly 1/4.
 */

Reference: https://leetcode.com/problems...

云服务器 GPU云服务器 Reservoir pick LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72311.html

leetcode398. Random Pick Index

摘要：思路一的实现其实要是想在的时间内完成随机数的获取，只需要缓存每个数字出现的下标，但是这意味着需要先对数据进行遍历，并且还需要的空间来额外存储数字下标的集合。所以我们只能每次在获取数字的时候来统计数字出现的次数，然后针对次数获取随机数下标。题目要求 Given an array of integers with possible duplicates, randomly output ...

airborne007 2019-08-16 15:07 评论0 收藏0
leetcode382. Linked List Random Node

摘要：题目要求要求从单链表中，随机返回一个节点的值，要求每个节点被选中的概率是相等的。假如一共有个物品，需要从其中挑选出个物品，要求确保个物品中每个物品都能够被等概率选中。对于这种等概率问题，简答的做法是通过随机数获取选中物品的下标。题目要求 Given a singly linked list, return a random nodes value from the linked li...

xiaodao 2019-08-16 17:58 评论0 收藏0
[LeetCode] 528. Random Pick with Weight

Problem Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight. Note: 1

wangjuntytl 2019-08-16 13:40 评论0 收藏0
关于codahale的HistogramMetric

摘要：百分位数第百分位数是这样一个值，它使得至少有的数据项小于或等于这个值，且至少有的数据项大于或等于这个值。即使极值变动大，相比其他几个，还是比较接近实际数据，曲线会有明显变动，不像其他的一段时间可能都是平滑的。基本概念 mean(平均值) 均值是就全部数据计算的,它具有优良的数学性质,是实际中应用最广泛的集中趋势测度值.其主要缺点是易受数据极端值的影响,对于偏态分布的数据,均值的代表性...

JiaXinYi 2019-08-14 17:41 评论0 收藏0
Python学习之路30-接口：从协议到抽象基类

摘要：本篇内容将从鸭子类型的动态协议，逐渐过渡到使接口更明确能验证实现是否符合规定的抽象基类。抽象基类介绍完动态实现接口后，现在开始讨论抽象基类，它属于静态显示地实现接口。标准库中的抽象基类从开始，标准库提供了抽象基类。《流畅的Python》笔记。本篇是面向对象惯用方法的第四篇，主要讨论接口。本篇内容将从鸭子类型的动态协议，逐渐过渡到使接口更明确、能验证实现是否符合规定的抽象基类(Abst...

LucasTwilight 2019-07-30 16:57 评论0 收藏0