AK F.*ing leetcode 流浪计划之加权随机数算法

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

本期话题：加权随机数算法

给定一个数组A。
要 求 实 现 取 到 数 字 i 的 概 率 为 A [ i ] s u m ( A ) 的 算 法 。 要求实现取到数字i的概率为frac {A[i]}{sum(A)}的算法。 要求实现取到数字i的概率为sum(A)A[i]​的算法。

可以对sum(A)进行分段，然后取个随机数如果落在第0段就取0，依此类推，如果落在第i段，就取i。

每一段可以使用前缀和来表示。

class WeightRandom {
    private:
    vector presum;
    int total;
    public:
    WeightRandom(){}
    // 初始
    WeightRandom(vector weights){
        presum.assign(weights.size(), 0);
        presum[0] = weights[0];
        total = weights[0];
        // 构造前缀和
        for(int i=1;i
            presum[i]=presum[i-1]+weights[i];
            total = presum[i];
        }
    }

    pair pick() {
        int n = rand()%total+1;
        int ind = lower_bound( presum.begin(), presum.end(),n)-presum.begin(); // 二分查找区间
        int num = n; // 在区间内具体位置。
        if(ind>0)num -= presum[ind-1];
        return pair({ind, num-1});
    }
};

链接：https://leetcode.cn/problems/random-pick-with-weight/

C++

class WeightRandom {
    private:
    vector presum;
    int total;
    public:
    WeightRandom(){}
    WeightRandom(vector weights){
        presum.assign(weights.size(), 0);
        presum[0] = weights[0];
        total = weights[0];
        for(int i=1;i
            presum[i]=presum[i-1]+weights[i];
            total = presum[i];
        }
    }

    pair pick() {
        int n = rand()%total+1;
        int ind = lower_bound( presum.begin(), presum.end(),n)-presum.begin();
        int num = n;
        if(ind>0)num -= presum[ind-1];
        return pair({ind, num-1});
    }
};

class Solution {
    WeightRandom wr;
public:
    Solution(vector& w) {
        wr = WeightRandom(w);
    }
    
    int pickIndex() {
        auto p = wr.pick();
        return p.first;
    }
};

链接：https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles/

C++

class WeightRandom {
    private:
    vector presum;
    int total;
    public:
    WeightRandom(){}
    WeightRandom(vector weights){
        presum.assign(weights.size(), 0);
        presum[0] = weights[0];
        total = weights[0];
        for(int i=1;i
            presum[i]=presum[i-1]+weights[i];
            total = presum[i];
        }
    }

    pair pick() {
        int n = rand()%total+1;
        int ind = lower_bound( presum.begin(), presum.end(),n)-presum.begin();
        int num = n;
        if(ind>0)num -= presum[ind-1];
        return pair({ind, num-1});
    }
};

class Solution {
    private:
    WeightRandom wr;
    vector> re;
public:
    Solution(vector>& rects) {
        re = rects;
        vector weights;
        for(auto v: rects) {
            weights.push_back((v[2]-v[0]+1)*(v[3]-v[1]+1));
        }
        wr = WeightRandom(weights);
    }
    
    vector pick() {
        auto ans = vector(2);

        auto p = wr.pick();

        int rows = re[p.first][3]-re[p.first][1]+1;
        int cols = re[p.first][2]-re[p.first][0]+1;

        ans[0] = re[p.first][0] + p.second%cols;
        ans[1] = re[p.first][1] + p.second/cols;

        return ans;
    }
};

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。