資訊專欄INFORMATION COLUMN
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 <= w.length <= 10000 1 <= w[i] <= 10^5 pickIndex will be called at most 10000 times.
Example 1:
Input: ["Solution","pickIndex"] [[[1]],[]] Output: [null,0]
Example 2:
Input: ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output: [null,0,1,1,1,0]
Explanation of Input Syntax:
The input is two lists: the subroutines called and their arguments. Solution"s constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren"t any.
Solutioncreate an array sum, to save sum of weights
create a Random random to create random in a range
the range should be [1, maxValue] as [1, sum[len-1]]
use Random.nextInt(maxValue) + 1 to get a random num of the range
use binary search to find the index of random in sum array
class Solution {
int[] sums;
int max;
Random random;
public Solution(int[] w) {
sums = new int[w.length];
sums[0] = w[0];
for (int i = 1; i < sums.length; i++) {
sums[i] = sums[i-1]+w[i];
}
max = sums[sums.length-1];
random = new Random();
}
public int pickIndex() {
int rand = random.nextInt(max)+1;
int index = findIndex(sums, rand);
return index;
}
private int findIndex(int[] nums, int k) {
int start = 0, end = nums.length-1;
while (start+1 < end) {
int mid = start+(end-start)/2;
if (nums[mid] == k) return mid;
else if (nums[mid] < k) start = mid+1;
else end = mid-1;
}
if (k > nums[end]) return end+1;
else if (k > nums[start]) return start+1;
else return start;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/72117.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...
摘要：思路一的實現(xiàn)其實要是想在的時間內(nèi)完成隨機(jī)數(shù)的獲取，只需要緩存每個數(shù)字出現(xiàn)的下標(biāo)，但是這意味著需要先對數(shù)據(jù)進(jìn)行遍歷，并且還需要的空間來額外存儲數(shù)字下標(biāo)的集合。所以我們只能每次在獲取數(shù)字的時候來統(tǒng)計數(shù)字出現(xiàn)的次數(shù)，然后針對次數(shù)獲取隨機(jī)數(shù)下標(biāo)。 題目要求 Given an array of integers with possible duplicates, randomly output ...
摘要：題目要求要求從單鏈表中，隨機(jī)返回一個節(jié)點的值，要求每個節(jié)點被選中的概率是相等的。假如一共有個物品，需要從其中挑選出個物品，要求確保個物品中每個物品都能夠被等概率選中。對于這種等概率問題，簡答的做法是通過隨機(jī)數(shù)獲取選中物品的下標(biāo)。 題目要求 Given a singly linked list, return a random nodes value from the linked li...
摘要：在本教程中，我們將學(xué)習(xí)如何使用八叉樹在點云數(shù)據(jù)中進(jìn)行空間分區(qū)和鄰居搜索。因此，搜索點和搜索結(jié)果之間的距離取決于八叉樹的分辨率參數(shù)。此外，先進(jìn)的內(nèi)存管理減少了八叉樹構(gòu)建過程中的內(nèi)存分配和釋放操作?？偨Y(jié)八叉樹實現(xiàn)是空間分區(qū)和搜索操作的強(qiáng)大工具。 本教程代碼開源：GitHub 歡迎st...
摘要：大體意思就是，先復(fù)制到，順便將所有的放在再復(fù)制所有的到，順便將所有的放在最后令，令，將和分離，返回的頭結(jié)點 Problem A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. ...
閱讀 728·2021-11-23 09:51
閱讀 3619·2021-10-11 10:58
閱讀 15973·2021-09-29 09:47
閱讀 3704·2021-09-01 11:42
閱讀 1371·2019-08-29 16:43
閱讀 1891·2019-08-29 15:37
閱讀 2184·2019-08-29 12:56
閱讀 1791·2019-08-28 18:21
