LeetCode 528 按权重随机选择

本文主要是介绍LeetCode 528 按权重随机选择，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

按权重随机选择

题目

思路

记录各元素前缀和和权重总和，现随机，再二分。

代码

class Solution {
public:vector<int>* pre;Solution(vector<int>& w) {pre=new vector<int>(w.size());int sum=0;for(int i=0;i<w.size();i++){sum+=w[i];(*pre)[i]=sum;}}int pickIndex() {int suiji=rand()%pre->back();int l=0,r=pre->size()-1;while(l<r){int mid=l+(r-l)/2;if((*pre)[mid]<=suiji) l=mid+1;else r=mid;}return l;}
};/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(w);* int param_1 = obj->pickIndex();*/

这篇关于LeetCode 528 按权重随机选择的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---