首页 > 其他分享 >LCR 071. 按权重随机选择

LCR 071. 按权重随机选择

时间:2024-03-17 16:11:48浏览次数:20  
标签:__ 下标 071 self random rank 随机 LCR sum

题目:给定一个正整数数组 w ,其中 w[i] 代表下标 i 的权重(下标从 0 开始),请写一个函数 pickIndex ,它可以随机地获取下标 i,选取下标 i 的概率与 w[i] 成正比。
例如,对于 w = [1, 3],挑选下标 0 的概率为 1 / (1 + 3) = 0.25 (即,25%),而选取下标 1 的概率为 3 / (1 + 3) = 0.75(即,75%)。
也就是说,选取下标 i 的概率为 w[i] / sum(w) 。

题解
这道题考察的主要知识点是前缀和和二分查找
主要分成三个步骤:

  1. 求出权重比率
  2. 在0到1之间生成随机数
  3. 求该随机数对应的最小index
class Solution:
    def __init__(self, w: List[int]):
        self.w = w
        self.index = [i for i in range(len(self.w))]
        total_sum = sum(self.w)
        self.rate = [weight / total_sum for weight in self.w]

    def pickIndex(self) -> int:
        start = 0.0
        random_num = random.random()
        for idx, score in enumerate(self.rate):
            start += score
            if random_num <= start:
                return self.index[idx]

但是这样查找的效率很低,最好是使用二分查找,在python中已经封装好了二分查找,可以直接使用

## 这是目前最优的算法
class Solution:

    def __init__(self, w: List[int]):
        self.w = w 
        self.rank = [w[0]]
        for i in range(1,len(self.w)):
            self.rank.append(self.rank[-1] + self.w[i]) ## 只用了一个循环
        

    def pickIndex(self) -> int:
        r = random.randint(1,self.rank[-1])
        return bisect.bisect_left(self.rank,r)
# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()

标签:__,下标,071,self,random,rank,随机,LCR,sum
From: https://www.cnblogs.com/zhumeili/p/18078693

相关文章

  • 基于减法平均算法改进的随机森林分类算法 - 附代码
    基于减法平均算法改进的随机森林分类算法-附代码文章目录基于减法平均算法改进的随机森林分类算法-附代码1.数据集2.RF模型3.基于减法平均算法优化的RF4.测试结果5.Matlab代码摘要:为了提高随机森林数据的分类预测准确率,对随机森林中的树木个数和最小叶子点数参......
  • [C++] C++生成随机数
    一、简介在C语言中常使用srand()+random()的方式生成随机数,该方式并不是一个很好的随据说生成方法,一方面是因为其生成的随机数质量较低,另一方面其随机数范围也有所限制。在C++11中推荐使用随机数引擎的方式生成随机数。如何高效得生成高质量得随机数(甚至需要满足指定分布)是一个......
  • 考虑源荷随机特征的热电联供微网优化(含matlab程序)
    目录一、前言二、含可再生能源的CHP型微网系统三、CCP理论四、具体模型五、不含随机变量分析的matlab程序设计1.粒子群寻优功能代码段2.目标函数子程序3.其他代码段六、基于CCP的粒子群优化程序1.含随机变量的约束条件处理2.随机变量生成 3.置信水平检验部分七......
  • golang 随机数组的性能对比测试
    最近需要用到随机数,但在随机数的生成方面遇到些问题,如加了seed后反而生成的数组是固定的,没有加是随机的,后面查资料了解到,如果seed值是一样的,序列中的值就固定的,而不加seed时,每次的都是随机的,后面想到如果用来做负载均衡呢,性能又如何。下面是源码:packagebenchimport( ......
  • 8分SCI | 揭示随机森林的解释奥秘:探讨LIME技术如何提高模型的可解释性与可信度!
    一、引言LocalInterpretableModel-agnosticExplanations(LIME)技术作为一种局部可解释性方法,能够解释机器学习模型的预测结果,并提供针对单个样本的解释。通过生成局部线性模型来近似原始模型的预测,LIME技术可以帮助用户理解模型在特定样本上的决策过程,提高模型的可解......
  • JS:随机点名综合案例
    需求:1、随机点名2、不能重复出现已经被抽取的名字3、当剩下最后一个人的名字时不再抽取部分html代码:<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0......
  • LCR 016. 无重复字符的最长子串(中)
    目录题目题解:滑动窗口题目给定一个字符串s,请你找出其中不含有重复字符的最长连续子字符串的长度。示例1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子字符串是"abc",所以其长度为3示例2:输入:s="bbbbb"输出:1解释:因为无重复字符的最长子字......
  • LCR 159. 库存管理 IIIc
    经典快排/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/intdivide(int*a,inthead,inttail){intt=a[head];while(head<tail){while(head<tail&&a[tail]>t)tail--;if(head<tail)......
  • 基于广义正态分布算法改进的随机森林分类算法 - 附代码
    基于广义正态分布算法改进的随机森林分类算法-附代码文章目录基于广义正态分布算法改进的随机森林分类算法-附代码1.数据集2.RF模型3.基于广义正态分布算法优化的RF4.测试结果5.Matlab代码摘要:为了提高随机森林数据的分类预测准确率,对随机森林中的树木个数和最......
  • 基于人工蜂鸟算法改进的随机森林分类算法 - 附代码
    基于人工蜂鸟算法改进的随机森林分类算法-附代码文章目录基于人工蜂鸟算法改进的随机森林分类算法-附代码1.数据集2.RF模型3.基于人工蜂鸟算法优化的RF4.测试结果5.Matlab代码摘要:为了提高随机森林数据的分类预测准确率,对随机森林中的树木个数和最小叶子点数参......