跳至主要内容

8.5 隨機與取樣

384. Shuffle an Array​

題目描述​

給定一個陣列，要求實現兩個指令函數。第一個函數「shuffle」可以隨機打亂這個陣列，第二個函數「reset」可以恢復原來的順序。

輸入輸出範例​

輸入是一個存有整數數字的陣列，以及一個包含指令函數名稱的陣列。輸出是一個二維陣列，表示每個指令生成的陣列。

Input: nums = [1,2,3], actions: ["shuffle","shuffle","reset"]
Output: [[2,1,3],[3,2,1],[1,2,3]]

在這個範例中，前兩次打亂的結果只要是隨機生成即可。

題解​

我們採用經典的 Fisher-Yates 洗牌算法，其原理是通過隨機交換位置來實現隨機打亂，有正向和反向兩種寫法，且實現非常方便。注意這裡「reset」函數以及 Solution 類的構造函數的實現細節。

class Solution {
   public:
    Solution(vector<int> nums) : nums_(nums) {}

    vector<int> reset() { return nums_; }

    vector<int> shuffle() {
        vector<int> shuffled(nums_);
        int n = nums_.size();
        // 可以使用反向或者正向洗牌，效果相同。
        // 反向洗牌：
        for (int i = n - 1; i >= 0; --i) {
            swap(shuffled[i], shuffled[rand() % (i + 1)]);
        }
        // 正向洗牌：
        // for (int i = 0; i < n; ++i) {
        // int pos = rand() % (n - i);
        // swap(shuffled[i], shuffled[i+pos]);
        // }
        return shuffled;
    }

   private:
    vector<int> nums_;
};

528. Random Pick with Weight​

題目描述​

給定一個陣列，陣列每個位置的值表示該位置的權重，要求按照權重的概率去隨機抽樣。

輸入輸出範例​

輸入是一維正整數陣列，表示權重；以及一個包含指令字串的一維陣列，表示運行幾次隨機抽樣。輸出是一維整數陣列，表示隨機抽樣的整數在陣列中的位置。

Input: weights = [1,3], actions: ["pickIndex","pickIndex","pickIndex"]
Output: [0,1,1]

在這個範例中，每次選擇的位置都是不確定的，但選擇第 0 個位置的期望為 1/4，選擇第 1 個位置的期望為 3/4。

題解​

我們可以先使用前綴和（partial_sum）計算到每個位置為止之前所有數字的總和，這個結果對於正整數陣列是單調遞增的。每當需要抽樣時，我們可以先隨機生成一個數字，然後使用二分法查找該數字在前綴和中的位置，以模擬加權抽樣的過程。這裡的二分法可以用 lower_bound 實現。

以範例為例，權重陣列 [1,3] 的前綴和為 [1,4]。如果我們隨機生成的數字為 1，那麼 lower_bound 返回的位置為 0；如果我們隨機生成的數字是 2、3、4，那麼 lower_bound 返回的位置為 1。

關於前綴和的更多技巧，我們將在接下來的章節中繼續深入講解。

class Solution {
   public:
    Solution(vector<int> weights) : cumsum_(weights) {
        partial_sum(cumsum_.begin(), cumsum_.end(), cumsum_.begin());
    }

    int pickIndex() {
        int val = (rand() % cumsum_.back()) + 1;
        return lower_bound(cumsum_.begin(), cumsum_.end(), val) -
               cumsum_.begin();
    }

   private:
    vector<int> cumsum_;
};

382. Linked List Random Node​

題目描述​

給定一個單向鏈結串列，要求設計一個演算法，可以隨機取得其中的一個數字。

輸入輸出範例​

輸入是一個單向鏈結串列，輸出是一個數字，表示鏈結串列裡其中一個節點的值。

Input: 1->2->3->4->5
Output: 3

在這個範例中，我們有均等的概率得到任意一個節點，比如 3。

題解​

不同於陣列，在未遍歷完鏈結串列前，我們無法知道鏈結串列的總長度。這裡我們可以使用水庫抽樣：遍歷一次鏈結串列，在遍歷到第 mm 個節點時，有 1m\frac{1}{m} 的概率選擇這個節點覆蓋掉之前的選擇。

我們提供一個簡單的，對於水庫算法隨機性的證明。對於長度為 nn 的鏈結串列的第 mm 個節點，最後被抽樣的充要條件是它被選擇，且之後的節點都沒有被選擇。這種情況發生的概率為：

1m×mm+1×m+1m+2×⋅⋅⋅×n−1n=1n\frac{1}{m} × \frac{m}{m+1} × \frac{m+1}{m+2} × · · · × \frac{n−1}{n} = \frac{1}{n}

因此每個點都有均等的概率被選擇。

當然，這道題我們也可以預處理鏈結串列，遍歷一遍之後把它轉化成陣列。

class Solution {
   public:
    Solution(ListNode* node) : head_(node) {}

    int getRandom() {
        int pick = head_->val;
        ListNode* node = head_->next;
        int i = 2;
        while (node) {
            if (rand() % i == 0) {
                pick = node->val;
            }
            ++i;
            node = node->next;
        }
        return pick;
    }

   private:
    ListNode* head_;
};