先說(shuō)結(jié)論,當(dāng)你遇到第i
個(gè)元素時(shí),應(yīng)該有1/i
的概率選擇該元素,1 - 1/i
的概率保持原有的選擇 ??创a容易理解這個(gè)思路:
/* 返回鏈表中一個(gè)隨機(jī)節(jié)點(diǎn)的值 */
int getRandom(ListNode head) {
Random r = new Random();
int i = 0, res = 0;
ListNode p = head;
// while 循環(huán)遍歷鏈表
while (p != null) {
i++;
// 生成一個(gè) [0, i) 之間的整數(shù)
// 這個(gè)整數(shù)等于 0 的概率就是 1/i
if (0 == r.nextInt(i)) {
res = p.val;
}
p = p.next;
}
return res;
}
對(duì)于概率算法,代碼往往都是很淺顯的,但是這種問(wèn)題的關(guān)鍵在于證明,你的算法為什么是對(duì)的?為什么每次以1/i
的概率更新結(jié)果就可以保證結(jié)果是平均隨機(jī)的?
我們來(lái)證明一下,假設(shè)總共有n
個(gè)元素,我們要的隨機(jī)性無(wú)非就是每個(gè)元素被選擇的概率都是1/n
對(duì)吧,那么對(duì)于第i
個(gè)元素,它被選擇的概率就是:
第i
個(gè)元素被選擇的概率是1/i
,在第i+1
次不被替換的概率是1 - 1/(i+1)
,在第i+2
次不被替換的概率是1 - 1/(i+2)
,以此類推,相乘的結(jié)果是第i
個(gè)元素最終被選中的概率,也就是1/n
。因此,該算法的邏輯是正確的。
同理,如果要在單鏈表中隨機(jī)選擇k
個(gè)數(shù),只要在第i
個(gè)元素處以k/i
的概率選擇該元素,以1 - k/i
的概率保持原有選擇即可 。代碼如下:
/* 返回鏈表中 k 個(gè)隨機(jī)節(jié)點(diǎn)的值 */
int[] getRandom(ListNode head, int k) {
Random r = new Random();
int[] res = new int[k];
ListNode p = head;
// 前 k 個(gè)元素先默認(rèn)選上
for (int i = 0; i < k && p != null; i++) {
res[i] = p.val;
p = p.next;
}
int i = k;
// while 循環(huán)遍歷鏈表
while (p != null) {
i++;
// 生成一個(gè) [0, i) 之間的整數(shù)
int j = r.nextInt(i);
// 這個(gè)整數(shù)小于 k 的概率就是 k/i
if (j < k) {
res[j] = p.val;
}
p = p.next;
}
return res;
}
對(duì)于數(shù)學(xué)證明,和上面區(qū)別不大:
雖然每次更新選擇的概率增大了k
倍,但是選到具體第i
個(gè)元素的概率還是要乘1/k
,也就回到了上一個(gè)推導(dǎo)。
類似的,回到掃雷游戲的隨機(jī)初始化問(wèn)題,我們可以寫(xiě)一個(gè)這樣的sample
抽樣函數(shù):
// 在區(qū)間 [lo, hi) 中隨機(jī)抽取 k 個(gè)數(shù)字
int[] sample(int lo, int hi, int k) {
Random r = new Random();
int[] res = new int[k];
// 前 k 個(gè)元素先默認(rèn)選上
for (int i = 0; i < k; i++) {
res[i] = lo + i;
}
int i = k;
// while 循環(huán)遍歷數(shù)字區(qū)間
while (i < hi - lo) {
i++;
// 生成一個(gè) [0, i) 之間的整數(shù)
int j = r.nextInt(i);
// 這個(gè)整數(shù)小于 k 的概率就是 k/i
if (j < k) {
res[j] = lo + i - 1;
}
}
return res;
}
這個(gè)函數(shù)能夠在一定的區(qū)間內(nèi)隨機(jī)選擇k
個(gè)數(shù)字,確保抽樣結(jié)果是均勻隨機(jī)的且只需要 O(N) 的時(shí)間復(fù)雜度。
蒙特卡洛驗(yàn)證法
上面講到的洗牌算法和水塘抽樣算法都屬于隨機(jī)概率算法,雖然從數(shù)學(xué)上推導(dǎo)上可以證明算法的思路是正確的,但如果你筆誤寫(xiě)出 bug,就會(huì)導(dǎo)致概率上的不均等。更神奇的是,力扣的判題機(jī)制能夠檢測(cè)出這種概率錯(cuò)誤。
那么最后我就來(lái)介紹一種方法檢測(cè)隨機(jī)算法的正確性:蒙特卡洛方法。我猜測(cè)力扣的判題系統(tǒng)也是利用這個(gè)方法來(lái)判斷隨機(jī)算法的正確性的。
記得高中有道數(shù)學(xué)題:往一個(gè)正方形里面隨機(jī)打點(diǎn),這個(gè)正方形里緊貼著一個(gè)圓,告訴你打點(diǎn)的總數(shù)和落在圓里的點(diǎn)的數(shù)量,讓你計(jì)算圓周率。
這其實(shí)就是利用了蒙特卡羅方法:當(dāng)打的點(diǎn)足夠多的時(shí)候,點(diǎn)的數(shù)量就可以近似代表圖形的面積。結(jié)合面積公式,可以很容易通過(guò)正方形和圓中點(diǎn)的數(shù)量比值推出圓周率的。
當(dāng)然,打的點(diǎn)越多,算出的圓周率越準(zhǔn)確,充分體現(xiàn)了大力出奇跡的道理。
比如,我們可以這樣檢驗(yàn)水塘抽樣算法sample
函數(shù)的正確性:
public static void main(String[] args) {
// 在 [12, 22) 中隨機(jī)選 3 個(gè)數(shù)
int lo = 12, hi = 22, k = 3;
// 記錄每個(gè)元素被選中的次數(shù)
int[] count = new int[hi - lo];
// 重復(fù) 10 萬(wàn)次
int N = 1000000;
for (int i = 0; i < N; i++) {
int[] res = sample(lo, hi, k);
for (int elem : res) {
// 對(duì)隨機(jī)選取的元素進(jìn)行記錄
count[elem - lo]++;
}
}
System.out.println(Arrays.toString(count));
}
這段代碼的輸出如下:
[300821, 299598, 299792, 299198, 299510, 300789, 300022, 300326, 299362, 300582]
當(dāng)然你可以做更細(xì)致的檢查,不過(guò)粗略看看,各個(gè)元素被選中的次數(shù)大致是相同的,這個(gè)算法實(shí)現(xiàn)的應(yīng)該沒(méi)啥問(wèn)題。
對(duì)于洗牌算法中的shuffle
函數(shù)也可以采取類似的驗(yàn)證方法,我們可以跟蹤某一個(gè)元素x
被打亂后的索引位置,如果x
落在各個(gè)索引的次數(shù)基本相同,則說(shuō)明算法正確,你可以自己嘗試實(shí)現(xiàn),我就不貼代碼驗(yàn)證了。
拓展延伸
到這里,常見(jiàn)的隨機(jī)算法就講完了,簡(jiǎn)單總結(jié)下吧。
洗牌算法主要用于打亂數(shù)組,比如我們?cè)?快速排序詳解及運(yùn)用中就用到了洗牌算法保證快速排序的效率。
水塘抽樣算法的運(yùn)用更加廣泛,可以在序列中隨機(jī)選擇若干元素,且能保證每個(gè)元素被選中的概率均等。
對(duì)于這些隨機(jī)概率算法,我們可以用蒙特卡洛方法檢驗(yàn)其正確性。
最后留幾個(gè)拓展題目:
1、本文開(kāi)頭講到了將二維數(shù)組坐標(biāo)(x, y)
轉(zhuǎn)化成一維數(shù)組索引的技巧,那么你是否有辦法把三維坐標(biāo)(x, y, z)
轉(zhuǎn)化成一維數(shù)組的索引呢?
2、如何對(duì)帶有權(quán)重的樣本進(jìn)行加權(quán)隨機(jī)抽?。勘热缃o你一個(gè)數(shù)組w
,每個(gè)元素w[i]
代表權(quán)重,請(qǐng)你寫(xiě)一個(gè)算法,按照權(quán)重隨機(jī)抽取索引。比如w = [1,99]
,算法抽到索引 0 的概率是 1%,抽到索引 1 的概率是 99%。
3、實(shí)現(xiàn)一個(gè)生成器類,構(gòu)造函數(shù)傳入一個(gè)很長(zhǎng)的數(shù)組,請(qǐng)你實(shí)現(xiàn)randomGet
方法,每次調(diào)用隨機(jī)返回?cái)?shù)組中的一個(gè)元素,多次調(diào)用不能重復(fù)返回相同索引的元素。要求不能對(duì)該數(shù)組進(jìn)行任何形式的修改,且操作的時(shí)間復(fù)雜度是 O(1)
-
算法
+關(guān)注
關(guān)注
23文章
4576瀏覽量
92341 -
游戲
+關(guān)注
關(guān)注
2文章
726瀏覽量
26245 -
隨機(jī)
+關(guān)注
關(guān)注
0文章
12瀏覽量
9722
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論