[LeetCode] 398. Random Pick Index (Reservoir Sampl

edagarli 發(fā)布于2019-08-16 13:46 / 651人閱讀

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云服務(wù)器云服務(wù)器 Reservoir pick LeetCode LeetCode_String

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72311.html

發(fā)表評論

登陸后可評論

0條評論

edagarli

男|高級講師

我要關(guān)注我要私信

TA的文章

#yyds干貨盤點(diǎn)# 前端基礎(chǔ)知識面試集錦2

閱讀 3057·2021-11-22 15:29
電子設(shè)備及半導(dǎo)體測量之“納米結(jié)構(gòu)的低級測量”技術(shù)說明

閱讀 1741·2021-10-12 10:11
指南者stm32單片機(jī)keil5新建工程和組織目錄的那些事

閱讀 1776·2021-09-04 16:45
Namesilo：域名購買及使用教程（附 Namesilo 優(yōu)惠碼）

閱讀 2256·2021-08-25 09:39
ION：2周年促銷，VPS年付8折優(yōu)惠，可選洛杉磯/圣何塞cn2 gia/新加坡cn2

閱讀 2801·2021-08-18 10:20
edgenat：全新“韓國原生IP”VPS，全場8折促銷，韓國CN2/中國香港CN2/洛杉磯CN2

閱讀 2526·2021-08-11 11:17
SASS入門

閱讀 456·2019-08-30 12:49
前端碎語（6）

閱讀 3318·2019-08-30 12:49

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

[LeetCode] 398. Random Pick Index (Reservoir Sampl

相關(guān)文章