簡述游戲中常用的兩種隨機(jī)算法（下）

先說結(jié)論，當(dāng)你遇到第i個元素時，應(yīng)該有1/i的概率選擇該元素，1 - 1/i的概率保持原有的選擇 ?？创a容易理解這個思路：

/* 返回鏈表中一個隨機(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++;
        // 生成一個 [0, i) 之間的整數(shù)
        // 這個整數(shù)等于 0 的概率就是 1/i
        if (0 == r.nextInt(i)) {
            res = p.val;
        }
        p = p.next;
    }
    return res;
}

對于概率算法，代碼往往都是很淺顯的，但是這種問題的關(guān)鍵在于證明，你的算法為什么是對的？為什么每次以1/i的概率更新結(jié)果就可以保證結(jié)果是平均隨機(jī)的？

我們來證明一下，假設(shè)總共有n個元素，我們要的隨機(jī)性無非就是每個元素被選擇的概率都是1/n對吧，那么對于第i個元素，它被選擇的概率就是：

第i個元素被選擇的概率是1/i，在第i+1次不被替換的概率是1 - 1/(i+1)，在第i+2次不被替換的概率是1 - 1/(i+2)，以此類推，相乘的結(jié)果是第i個元素最終被選中的概率，也就是1/n。因此，該算法的邏輯是正確的。

同理，如果要在單鏈表中隨機(jī)選擇k個數(shù)，只要在第i個元素處以k/i的概率選擇該元素，以1 - k/i的概率保持原有選擇即可 。代碼如下：

/* 返回鏈表中 k 個隨機(jī)節(jié)點(diǎn)的值 */
int[] getRandom(ListNode head, int k) {
    Random r = new Random();
    int[] res = new int[k];
    ListNode p = head;

    // 前 k 個元素先默認(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++;
        // 生成一個 [0, i) 之間的整數(shù)
        int j = r.nextInt(i);
        // 這個整數(shù)小于 k 的概率就是 k/i
        if (j < k) {
            res[j] = p.val;
        }
        p = p.next;
    }
    return res;
}

對于數(shù)學(xué)證明，和上面區(qū)別不大：

雖然每次更新選擇的概率增大了k倍，但是選到具體第i個元素的概率還是要乘1/k，也就回到了上一個推導(dǎo)。

類似的，回到掃雷游戲的隨機(jī)初始化問題，我們可以寫一個這樣的sample抽樣函數(shù)：

// 在區(qū)間 [lo, hi) 中隨機(jī)抽取 k 個數(shù)字
int[] sample(int lo, int hi, int k) {
    Random r = new Random();
    int[] res = new int[k];

    // 前 k 個元素先默認(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++;
        // 生成一個 [0, i) 之間的整數(shù)
        int j = r.nextInt(i);
        // 這個整數(shù)小于 k 的概率就是 k/i
        if (j < k) {
            res[j] = lo + i - 1;
        }
    }
    return res;
}

這個函數(shù)能夠在一定的區(qū)間內(nèi)隨機(jī)選擇k個數(shù)字，確保抽樣結(jié)果是均勻隨機(jī)的且只需要 O(N) 的時間復(fù)雜度。

蒙特卡洛驗(yàn)證法

上面講到的洗牌算法和水塘抽樣算法都屬于隨機(jī)概率算法，雖然從數(shù)學(xué)上推導(dǎo)上可以證明算法的思路是正確的，但如果你筆誤寫出 bug，就會導(dǎo)致概率上的不均等。更神奇的是，力扣的判題機(jī)制能夠檢測出這種概率錯誤。

那么最后我就來介紹一種方法檢測隨機(jī)算法的正確性：蒙特卡洛方法。我猜測力扣的判題系統(tǒng)也是利用這個方法來判斷隨機(jī)算法的正確性的。

記得高中有道數(shù)學(xué)題：往一個正方形里面隨機(jī)打點(diǎn)，這個正方形里緊貼著一個圓，告訴你打點(diǎn)的總數(shù)和落在圓里的點(diǎn)的數(shù)量，讓你計(jì)算圓周率。

這其實(shí)就是利用了蒙特卡羅方法：當(dāng)打的點(diǎn)足夠多的時候，點(diǎn)的數(shù)量就可以近似代表圖形的面積。結(jié)合面積公式，可以很容易通過正方形和圓中點(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 個數(shù)
    int lo = 12, hi = 22, k = 3;
    // 記錄每個元素被選中的次數(shù)
    int[] count = new int[hi - lo];
    // 重復(fù) 10 萬次
    int N = 1000000;
    for (int i = 0; i < N; i++) {
        int[] res = sample(lo, hi, k);
        for (int elem : res) {
            // 對隨機(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ì)致的檢查，不過粗略看看，各個元素被選中的次數(shù)大致是相同的，這個算法實(shí)現(xiàn)的應(yīng)該沒啥問題。

對于洗牌算法中的shuffle函數(shù)也可以采取類似的驗(yàn)證方法，我們可以跟蹤某一個元素x被打亂后的索引位置，如果x落在各個索引的次數(shù)基本相同，則說明算法正確，你可以自己嘗試實(shí)現(xiàn)，我就不貼代碼驗(yàn)證了。

拓展延伸

到這里，常見的隨機(jī)算法就講完了，簡單總結(jié)下吧。

洗牌算法主要用于打亂數(shù)組，比如我們在 快速排序詳解及運(yùn)用中就用到了洗牌算法保證快速排序的效率。

水塘抽樣算法的運(yùn)用更加廣泛，可以在序列中隨機(jī)選擇若干元素，且能保證每個元素被選中的概率均等。

對于這些隨機(jī)概率算法，我們可以用蒙特卡洛方法檢驗(yàn)其正確性。

最后留幾個拓展題目：

1、本文開頭講到了將二維數(shù)組坐標(biāo)(x, y)轉(zhuǎn)化成一維數(shù)組索引的技巧，那么你是否有辦法把三維坐標(biāo)(x, y, z)轉(zhuǎn)化成一維數(shù)組的索引呢？

2、如何對帶有權(quán)重的樣本進(jìn)行加權(quán)隨機(jī)抽取？比如給你一個數(shù)組w，每個元素w[i]代表權(quán)重，請你寫一個算法，按照權(quán)重隨機(jī)抽取索引。比如w = [1,99]，算法抽到索引 0 的概率是 1%，抽到索引 1 的概率是 99%。

3、實(shí)現(xiàn)一個生成器類，構(gòu)造函數(shù)傳入一個很長的數(shù)組，請你實(shí)現(xiàn)randomGet方法，每次調(diào)用隨機(jī)返回?cái)?shù)組中的一個元素，多次調(diào)用不能重復(fù)返回相同索引的元素。要求不能對該數(shù)組進(jìn)行任何形式的修改，且操作的時間復(fù)雜度是 O(1)