資訊專欄INFORMATION COLUMN
摘要：思路一的實現(xiàn)其實要是想在的時間內(nèi)完成隨機數(shù)的獲取，只需要緩存每個數(shù)字出現(xiàn)的下標(biāo)，但是這意味著需要先對數(shù)據(jù)進行遍歷，并且還需要的空間來額外存儲數(shù)字下標(biāo)的集合。所以我們只能每次在獲取數(shù)字的時候來統(tǒng)計數(shù)字出現(xiàn)的次數(shù)，然后針對次數(shù)獲取隨機數(shù)下標(biāo)。
題目要求
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);
設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，使得從該數(shù)據(jù)結(jié)構(gòu)中查詢一個數(shù)字時，能夠以等概率返回該數(shù)字所在的任何下標(biāo)。額外的要求是只要占用O(1)的額外的空間復(fù)雜度。
思路一：O(2n)的實現(xiàn)其實要是想在O(1)的時間內(nèi)完成隨機數(shù)的獲取，只需要緩存每個數(shù)字出現(xiàn)的下標(biāo)，但是這意味著需要先對數(shù)據(jù)進行遍歷，并且還需要O(n)的空間來額外存儲數(shù)字下標(biāo)的集合。這違背了題目意思。所以我們只能每次在獲取數(shù)字的時候來統(tǒng)計數(shù)字出現(xiàn)的次數(shù)，然后針對次數(shù)獲取隨機數(shù)下標(biāo)。
代碼如下：
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
思路二：蓄水池問題
有沒有可能在一次的遍歷中，找到這個隨機下標(biāo)呢？這就涉及到一個概率問題，即當(dāng)我在遍歷過程中遇到這個數(shù)字時，我是否需要選擇它作為我的結(jié)果值。
首先介紹一下蓄水池抽樣算法。蓄水池抽樣算法主要對應(yīng)的是這樣的一個問題，假設(shè)有一個非常大的數(shù)據(jù)集，或者是一個以流的形式作為輸入的數(shù)據(jù)集，希望從中選擇K個樣本，此時我們可能無法把所有的樣本都放在內(nèi)存中，因此只能保存一個大小為K的集合，每次遇到一個數(shù)據(jù)時，決定是否將其放入樣本中。
因此，假設(shè)當(dāng)前遇到的數(shù)據(jù)總共有N個，如果N小于K，則每個數(shù)據(jù)被選中的概率為1，如果N>K，則每個數(shù)據(jù)被選中的概率為K/N，舊樣本中數(shù)據(jù)被保留的概率為1 - K(N-K)/N即K/N，因此每一個舊的數(shù)據(jù)被替換掉的概率為1/N。
按照這個思路，我們在下面的遍歷時，每遇到一個新元素，就判斷當(dāng)前選中的元素是否會被該元素替換掉即可。
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
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/73289.html
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...
摘要：題目要求要求從單鏈表中，隨機返回一個節(jié)點的值，要求每個節(jié)點被選中的概率是相等的。假如一共有個物品，需要從其中挑選出個物品，要求確保個物品中每個物品都能夠被等概率選中。對于這種等概率問題，簡答的做法是通過隨機數(shù)獲取選中物品的下標(biāo)。 題目要求 Given a singly linked list, return a random nodes value from the linked li...
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
摘要：本篇內(nèi)容將從鴨子類型的動態(tài)協(xié)議，逐漸過渡到使接口更明確能驗證實現(xiàn)是否符合規(guī)定的抽象基類。抽象基類介紹完動態(tài)實現(xiàn)接口后，現(xiàn)在開始討論抽象基類，它屬于靜態(tài)顯示地實現(xiàn)接口。標(biāo)準(zhǔn)庫中的抽象基類從開始，標(biāo)準(zhǔn)庫提供了抽象基類。 《流暢的Python》筆記。本篇是面向?qū)ο髴T用方法的第四篇，主要討論接口。本篇內(nèi)容將從鴨子類型的動態(tài)協(xié)議，逐漸過渡到使接口更明確、能驗證實現(xiàn)是否符合規(guī)定的抽象基類(Abst...
摘要：自己定義的抽象基類要繼承。抽象基類可以包含具體方法。這里想表達(dá)的觀點是我們可以偷懶，直接從抽象基類中繼承不是那么理想的具體方法。 抽象基類 抽象基類的常見用途： 實現(xiàn)接口時作為超類使用。 然后，說明抽象基類如何檢查具體子類是否符合接口定義，以及如何使用注冊機制聲明一個類實現(xiàn)了某個接口，而不進行子類化操作。 如何讓抽象基類自動識別任何符合接口的類——不進行子類化或注冊。 接口在動態(tài)類...
閱讀 1839·2021-09-28 09:46
閱讀 3157·2019-08-30 14:22
閱讀 1888·2019-08-26 13:36
閱讀 3355·2019-08-26 11:32
閱讀 2104·2019-08-23 16:56
閱讀 1161·2019-08-23 16:09
閱讀 1316·2019-08-23 12:55
閱讀 2163·2019-08-23 11:44
