leetcode398. Random Pick Index

airborne007 發布于2019-08-16 15:07 / 2580人閱讀

摘要：思路一的實現其實要是想在的時間內完成隨機數的獲取，只需要緩存每個數字出現的下標，但是這意味著需要先對數據進行遍歷，并且還需要的空間來額外存儲數字下標的集合。所以我們只能每次在獲取數字的時候來統計數字出現的次數，然后針對次數獲取隨機數下標。

題目要求

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);

設計一個數據結構，使得從該數據結構中查詢一個數字時，能夠以等概率返回該數字所在的任何下標。額外的要求是只要占用O(1)的額外的空間復雜度。

思路一：O(2n)的實現

其實要是想在O(1)的時間內完成隨機數的獲取，只需要緩存每個數字出現的下標，但是這意味著需要先對數據進行遍歷，并且還需要O(n)的空間來額外存儲數字下標的集合。這違背了題目意思。所以我們只能每次在獲取數字的時候來統計數字出現的次數，然后針對次數獲取隨機數下標。

代碼如下：

    private int[] nums;
    private Random r;
    public Solution(int[] nums) {
        this.nums = nums;
        this.r = new Random();
    }
    
    public int pick(int target) {
        int count = 0;
        int result = -1;
        for(int i = 0 ; i
思路二：蓄水池問題
有沒有可能在一次的遍歷中，找到這個隨機下標呢？這就涉及到一個概率問題，即當我在遍歷過程中遇到這個數字時，我是否需要選擇它作為我的結果值。
首先介紹一下蓄水池抽樣算法。蓄水池抽樣算法主要對應的是這樣的一個問題，假設有一個非常大的數據集，或者是一個以流的形式作為輸入的數據集，希望從中選擇K個樣本，此時我們可能無法把所有的樣本都放在內存中，因此只能保存一個大小為K的集合，每次遇到一個數據時，決定是否將其放入樣本中。
因此，假設當前遇到的數據總共有N個，如果N小于K，則每個數據被選中的概率為1，如果N>K，則每個數據被選中的概率為K/N，舊樣本中數據被保留的概率為1 - K(N-K)/N即K/N，因此每一個舊的數據被替換掉的概率為1/N。
按照這個思路，我們在下面的遍歷時，每遇到一個新元素，就判斷當前選中的元素是否會被該元素替換掉即可。
    private int[] nums;
    private Random r;
    public Solution(int[] nums) {
        this.nums = nums;
        this.r = new Random();
    }
    
    public int pick(int target) {
        int count = 0;
        int result = -1;
        for(int i = 0 ; i

GPU云服務器云服務器 pick Leetcod LeetCode LeetCode_String

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73289.html

[LeetCode] 398. Random Pick Index (Reservoir Sampl

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 siz...

edagarli 2019-08-16 13:46 評論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
Python學習之路30-接口：從協議到抽象基類

摘要：本篇內容將從鴨子類型的動態協議，逐漸過渡到使接口更明確能驗證實現是否符合規定的抽象基類。抽象基類介紹完動態實現接口后，現在開始討論抽象基類，它屬于靜態顯示地實現接口。標準庫中的抽象基類從開始，標準庫提供了抽象基類。《流暢的Python》筆記。本篇是面向對象慣用方法的第四篇，主要討論接口。本篇內容將從鴨子類型的動態協議，逐漸過渡到使接口更明確、能驗證實現是否符合規定的抽象基類(Abst...

LucasTwilight 2019-07-30 16:57 評論0 收藏0
流暢的python讀書筆記-第11章-接口：從協議到抽象基類

摘要：自己定義的抽象基類要繼承。抽象基類可以包含具體方法。這里想表達的觀點是我們可以偷懶，直接從抽象基類中繼承不是那么理想的具體方法。抽象基類抽象基類的常見用途：實現接口時作為超類使用。然后，說明抽象基類如何檢查具體子類是否符合接口定義，以及如何使用注冊機制聲明一個類實現了某個接口，而不進行子類化操作。如何讓抽象基類自動識別任何符合接口的類——不進行子類化或注冊。接口在動態類...

Kyxy 2019-07-30 16:38 評論0 收藏0