LeetCode 题解工作台
按权重随机选择
给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。 请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1 ）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / s…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
class Solution: def __init__(self, w: List[int]):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。
请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。
- 例如，对于
w = [1, 3]，挑选下标0的概率为1 / (1 + 3) = 0.25（即，25%），而选取下标1的概率为3 / (1 + 3) = 0.75（即，75%）。
示例 1：
输入： ["Solution","pickIndex"] [[[1]],[]] 输出： [null,0] 解释： Solution solution = new Solution([1]); solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。
示例 2：
输入： ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[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 <= 1041 <= w[i] <= 105pickIndex将被调用不超过104次
解题思路
方法一
class Solution:
def __init__(self, w: List[int]):
self.s = [0]
for c in w:
self.s.append(self.s[-1] + c)
def pickIndex(self) -> int:
x = random.randint(1, self.s[-1])
left, right = 1, len(self.s) - 1
while left < right:
mid = (left + right) >> 1
if self.s[mid] >= x:
right = mid
else:
left = mid + 1
return left - 1
# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for preprocessing prefix sums and O(log n) for each pickIndex call due to binary search. Space complexity is O(n) to store the prefix sum array. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Mentions of weighted probability or random selection indicate candidate understanding of array-to-probability mapping.
- question_mark
Candidate suggests prefix sums before random index generation showing grasp of cumulative distribution mapping.
- question_mark
Binary search on the prefix sum demonstrates correct application of the problem's primary pattern.
常见陷阱
外企场景- error
Using random number generation directly on indices without weight adjustment leads to incorrect probabilities.
- error
Iterating through weights linearly for each pickIndex causes O(n) per query instead of O(log n).
- error
Off-by-one errors when mapping random numbers to prefix sum ranges can skew probability distribution.
进阶变体
外企场景- arrow_right_alt
Changing the weight array dynamically requires segment trees or Fenwick trees for updates while keeping efficient pickIndex.
- arrow_right_alt
Picking k indices instead of one can be handled by repeated weighted selection with care to avoid repeated selection bias.
- arrow_right_alt
Handling very large weights may need careful data type selection or scaling to prevent integer overflow during prefix sum computation.