Random Pick with Weight สุ่มดัชนีตามน้ำหนักใน C++

ให้อาร์เรย์ w ของจำนวนเต็มบวก w[i] คือน้ำหนักของดัชนี i เขียนฟังก์ชัน pickIndex() ที่สุ่มดัชนีตามสัด่วนน้ำหนัก

ตัวอย่าง: w = [1,3] เรียก pickIndex() 5 ครั้ง → อาจได้ 0, 1, 1, 1, 0

วิธีแก้ปัญหา (Prefix Sum + Binary Search)

1. สร้าง prefix sum array: w[i] = w[i] + w[i-1]
2. สุ่มตัวเลข r ในช่วง [0, w.back()-1]
3. ใช้ upper_bound หาตำแหน่งแรกที่ > r
4. คืนค่าดัชนีนั้น

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int n;
    vector<int> v;
    
    Solution(vector<int>& w) {
        srand(time(NULL));
        n = w[0];
        for (int i = 1; i < w.size(); i++) {
            w[i] += w[i - 1];
            n = w[i];
        }
        v = w;
    }
    
    int pickIndex() {
        return upper_bound(v.begin(), v.end(), rand() % v.back()) - v.begin();
    }
};

int main() {
    vector<int> v = {1, 3};
    Solution ob(v);
    for (int i = 0; i < 5; i++) cout << ob.pickIndex() << endl;
    return 0;
}

Input

Initialize with [1, 3] and call pickIndex five times

Output

1 1 1 1 0