528. Random Pick with Weight - Medium

前往題目

想法

• 題目要求每次pickIndex的時候都根據機率return數值，例如[1,3]那return 1的機率就是$1 / (1 + 3)$，return 3的機率是$3 / (1 + 3)$
• 但是讓我困惑的是要怎麼根據機率return。算機率很簡單，只要弄個hashmap把每個機率存下來就好了；或是存sum，然後直接算也很快

思路

這題很妙…解法也有些不懂的地方

大致上就是把每個數字之間的區間拉成他們的數字比例，例如123會變成136，這樣1~3之間就有2，3~6之間就有3，也就是說彼此之間的距離就是原本的數字，因為根據題目的公式，數字越大代表權重大被選到的機率也就越大

1. 紀錄每個index的prefix sum
2. 選定一個隨機數，Binary search直到找到最接近隨機數的數字(但是要大於隨機數，如果等於那就直接是答案了)

這個演算法用想的實在是很反直覺，跟一般binary search有一點點的差異，r = mid而不是mid - 1因為mid有可能是答案，而且最後是回傳l而不是mid，但如果多加一句if (randNum == prefixSum[mid]) return mid其實也是accept的

Code

class Solution {

    private int total; // total sum of w[]
    private int[] prefixSum; // Prefix sum of every index

    public Solution(int[] w) {
        total = 0;
        prefixSum = new int[w.length];

        int tempTotal = 0;
        // Calculate prefixsum
        for (int i = 0; i < w.length; ++i) {
            tempTotal += w[i];
            prefixSum[i] = tempTotal;
        }
        total = tempTotal;
    }
    
    public int pickIndex() {
        // The random number
        int randNum = new Random().nextInt(total) + 1;
        // left and right pointer
        int l = 0, r = prefixSum.length - 1;
        int mid = 0;

        // The answer found when they meet
        while (l < r) {
            mid = l + (r - l) / 2;

            if (randNum > prefixSum[mid]){
                l = mid + 1;
            } else {
                r = mid; // Since mid might be the answer
            }
        }

        // Return left pointer
        return l;
    }
}

2024/05/07

• 權重random不知道怎麼弄，原來是要利用prefixSum