给定一个正整数数组 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:输入:inputs = ["Solution","pickIndex"] inputs = [[[1]],[]] 输出:[null,0]
解释:Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0,因为数组中只有一个元素,所以唯一的选择是返回下标 0。
示例 2:输入:inputs = ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
inputs = [[[1,3]],[],[],[],[],[]]
输出:[null,1,1,1,1,0]
解释:Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1,返回下标 1,返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0,返回下标 0,返回该下标概率为 1/4 。
由于这是一个随机问题,允许多个答案,因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。
提示:1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex 将被调用不超过 10000 次
注意:本题与主站 528 题相同:
1、前缀和+二分查找;时间复杂度O(n),空间复杂度O(n)
type Solution struct {
nums []int
total int
}
func Constructor(w []int) Solution {
total := 0
arr := make([]int, len(w)) // 前缀和
for i := 0; i < len(w); i++ {
total = total + w[i]
arr[i] = total
}
return Solution{
nums: arr,
total: total,
}
}
func (this *Solution) PickIndex() int {
target := rand.Intn(this.total)
left, right := 0, len(this.nums)
for left < right {
mid := left + (right-left)/2
if this.nums[mid] <= target {
left = mid + 1
} else {
right = mid
}
}
return left
}
Medium题目,题目同leetcode 528.按权重随机选择;类似的题目有:leetcode 497.非重叠矩形中的随机点
页面更新:2024-05-18
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号