LeetCode 528. Random Pick with Weight — JavaScript

我妹今天出發去史丹佛資工碩士,很了不起呢!

題目中例子2,權重為[1, 3],表示有兩個點,權重分別為1和3,那麼就是說一個點的出現概率是四分之一,另一個出現的概率是四分之三。由於我們的Math.random()函數是等概率的隨機,那麼我們如何才能有權重的隨機呢? 我們可以使用一個trick,由於權重是1和3,相加為4,那麼我們現在假設有4個點,然後隨機等概率取一個點,隨機到第一個點後就表示原來的第一個點,隨機到後三個點就表示原來的第二個點,這樣就可以保證有權重的隨機。那麼我們就可以建立權重數組的累加和數組,比如若權重數組為[1, 3, 2] 的話,那麼累加和數組為[1, 4, 6],整個的權重和為6,Math.random() * this.arr[this.arr.length-1],可以隨機出範圍[0, 5] 內的數,隨機到0 則為第一個點,隨機到1,2,3 則為第二個點,隨機到4,5 則為第三個點,所以我們隨機出一個數字target後,然後再累加和數組中查找第一個大於隨機數target的數字,使用二分查找法可以找到第一個大於隨機數target的數字的坐標,即為所求。

參考:https://www.cnblogs.com/grandyang/p/9784690.html

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
黃韋智

自學寫程式,目前爲 React 前端工程師。熱愛旅遊,將近 30 個國家,足跡遍佈亞洲與歐洲。生命與街舞已經離不開,歡迎訂閱 Youtube 頻道:https://www.youtube.com/channel/UCEU-bEDl7R-iGyLVZFae33g