528. Random Pick with Weight

1. 问题

给定一个权重数组w，w[i]表示下标i的权重，根据权重从数组中随机抽取下标。

2. 思路

这道题相当于 497. Random Point in Non-overlapping Rectangles的一个简化版。

（1）可以先依次对每个下标的权重累加存起来（相当于概率分布中的分布累积函数CDF，Cumulative Distribution Function）。

（2）从 [1, 总权重] 中随机取一个数n，根据这个数在多个累加权重之间寻找合适的位置，即可完成题目要求的随机采样。

（3）可以使用python的bisect_left方法，bisect_left的作用是对已排序数组，查找目标数值将会插入的位置并返回（但是不会插入），数值相同时返回靠左的位置。

init：时间复杂度O(n)，空间复杂度O(n)

pickIndex：时间复杂度O(n)，空间复杂度O(1)

3. 代码

import random

import bisect

class Solution(object):

    def __init__(self, w):

        """

        :type w: List[int]

        """

        self.accumulate = []

        sums = 0

        for weight in w:

            sums += weight

            self.accumulate.append(sums)

    def pickIndex(self):

        """

        :rtype: int

        """

        n = random.randint(1,self.accumulate[-1])

        i = bisect.bisect_left(self.accumulate, n)

        return i

# Your Solution object will be instantiated and called as such:

# obj = Solution(w)

# param_1 = obj.pickIndex()

4. 类似题目

497. Random Point in Non-overlapping Rectangles

巴特西

528. Random Pick with Weight

1. 问题

2. 思路

3. 代码

4. 类似题目

最新文章

热门文章