3 回答

TA貢獻(xiàn)1864條經(jīng)驗(yàn) 獲得超6個贊
我知道這是一個非常古老的問題,但是如果你應(yīng)用一點(diǎn)數(shù)學(xué),我認(rèn)為在O(n)時間有一個巧妙的技巧!
該指數(shù)分布有兩個非常有用的特性。
給定來自具有不同速率參數(shù)的不同指數(shù)分布的n個樣本,給定樣本的最小概率等于其速率參數(shù)除以所有速率參數(shù)的總和。
它是“無記憶的”。因此,如果您已經(jīng)知道最小值,那么任何剩余元素是第二個到最小值的概率與如果真正的最小值被移除(并且從未生成)的概率相同,那個元素將是新的分鐘。這看起來很明顯,但我認(rèn)為由于某些條件概率問題,其他分布可能不是這樣。
使用事實(shí)1,我們知道選擇單個元素可以通過生成速率參數(shù)等于權(quán)重的指數(shù)分布樣本,然后選擇具有最小值的指數(shù)分布樣本來完成。
使用事實(shí)2,我們知道我們不必重新生成指數(shù)樣本。相反,只需為每個元素生成一個元素,并使用最低樣本的k元素。
找到最低k可以在O(n)中完成。使用Quickselect算法查找第k個元素,然后簡單地再次通過所有元素并輸出低于第k個的所有元素。
一個有用的說明:如果您無法立即訪問庫以生成指數(shù)分布樣本,則可以通過以下方式輕松完成: -ln(rand())/weight
添加回答
舉報(bào)