0398. Random Pick Index¶
题目信息¶
- 题号:
0398
- 难度:
Medium
- 主题:
固定数组、重复值、随机下标、等概率
- 原题:
- 重点:
返回的是下标而不是值、目标保证存在、同值的所有下标概率相同、对象跨调用使用构造数组
题目重述¶
使用可能包含重复值的整数数组 nums 构造对象,并实现 pick(target)。每次调用时,随机返回一个满足 nums[index] == target 的零基下标。
target 保证至少在数组中出现一次。若它对应多个下标,每个符合条件的下标被返回的概率必须相同,而不是按不同数值等概率选择。数组长度位于 [1, 2 * 10^4],元素位于 32 位有符号整数范围内,pick 的调用次数不超过 10^4;构造后的数组内容在对象调用期间保持不变。
自建示例¶
目标出现三次:
输入数组:nums = [4,1,4,2,4]
调用:pick(4)
输出:0、2 或 4
解释:三个合法下标应各有 1/3 概率被返回。
目标只有一个位置:
输入数组:nums = [4,1,4,2,4]
调用:pick(2)
输出:3
解释:值 2 只出现在下标 3,因此每次调用都必须返回 3。
把目标值的所有下标预先分组¶
构造时建立“值到下标数组”的映射。调用 pick(target) 时,目标对应的每个下标在同一个连续数组中,随机选择其位置即可保证下标等概率;不需要按值抽样,因为题目要求的是目标值对应的实例位置。
C++ 实现¶
class Solution {
std::unordered_map<int, std::vector<int>> positions;
std::mt19937 generator{std::random_device{}()};
public:
Solution(std::vector<int>& nums) {
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
positions[nums[i]].push_back(i);
}
}
int pick(int target) {
const auto& candidates = positions[target];
std::uniform_int_distribution<int> distribution(
0, static_cast<int>(candidates.size()) - 1);
return candidates[distribution(generator)];
}
};
代码分析¶
构造阶段每个数组位置只加入一次,之后随机范围正好覆盖所有合法下标;目标保证存在,所以候选数组非空。构造时间为 O(n),每次 pick 平均为 O(1),额外空间为 O(n)。