398. 随机数索引

🟠   🔖  水塘抽样 哈希表 数学 随机化  🔗 力扣 LeetCode

题目

Given an integer array nums with possible duplicates , randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Implement the Solution class:

• Solution(int[] nums) Initializes the object with the array nums.
• int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i's, then each index should have an equal probability of returning.

Example 1:

Input

["Solution", "pick", "pick", "pick"]

[[[1, 2, 3, 3, 3]], [3], [1], [3]]

Output

[null, 4, 0, 2]

Explanation

Solution solution = new Solution([1, 2, 3, 3, 3]);

solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.

solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

Constraints:

• 1 <= nums.length <= 2 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• target is an integer from nums.
• At most 10^4 calls will be made to pick.

题目大意

给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。

实现 Solution 类：

• Solution(int[] nums) 用数组 nums 初始化对象。
• int pick(int target) 从 nums 中选出一个满足 nums[i] == target 的随机索引 i 。如果存在多个有效的索引，则每个索引的返回概率应当相等。

示例：

输入

["Solution", "pick", "pick", "pick"]

[[[1, 2, 3, 3, 3]], [3], [1], [3]]

输出

[null, 4, 0, 2]

解释

Solution solution = new Solution([1, 2, 3, 3, 3]);

solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。

solution.pick(1); // 返回 0 。因为只有 nums[0] 等于 1 。

solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。

提示：

• 1 <= nums.length <= 2 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• target 是 nums 中的一个整数
• 最多调用 pick 函数 10^4 次

解题思路

• 构造函数 (Solution)：
  • 预处理 nums 数组，将每个数字及其所有索引存入哈希表 Map，键为数字，值为索引数组。
• 随机索引选择 (pick)：
  • 获取 target 的索引数组 arr，使用 Math.floor(Math.random() * arr.length) 随机选取索引。

复杂度分析

• 时间复杂度：
  • 构造函数：O(n)
  • pick() 方法：O(1)
• 空间复杂度：O(n)，用于存储哈希表中的数字与索引映射。

代码

/**
 * @param {number[]} nums
 */
var Solution = function (nums) {
	this.map = new Map();
	for (let i = 0; i < nums.length; i++) {
		if (!this.map.has(nums[i])) {
			this.map.set(nums[i], []);
		}
		this.map.get(nums[i]).push(i);
	}
};

/**
 * @param {number} target
 * @return {number}
 */
Solution.prototype.pick = function (target) {
	const arr = this.map.get(target);
	return arr[Math.floor(Math.random() * arr.length)];
};

相关题目

题号	标题	题解	标签	难度	力扣
382	链表随机节点	[✓]	水塘抽样 链表 数学 1+	🟠	🀄️ 🔗
528	按权重随机选择	[✓]	数组 数学 二分查找 2+	🟠	🀄️ 🔗
710	黑名单中的随机数		数组 哈希表 数学 3+	🔴	🀄️ 🔗