[LeetCode] 398. Random Pick Index (Reservoir Sampl

edagarli 發布于2019-08-16 13:46 / 644人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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