Leetcode 398. 随机数索引

1.题目基本信息

1.1.题目描述

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

实现 Solution 类：

• Solution(int[] nums) 用数组 nums 初始化对象。

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

1.2.题目地址

https://leetcode.cn/problems/random-pick-index/description/

2.解题方法

2.1.解题思路

哈希表 / 鱼塘抽样

3.解题代码

哈希表方法代码

from collections import defaultdictclass Solution:# 思路2：哈希表def __init__(self, nums: List[int]):self.map1 = defaultdict(list)for i, num in enumerate(nums):self.map1[num].append(i)def pick(self, target: int) -> int:return random.choice(self.map1[target])

鱼塘抽样方法代码

class Solution:# 思路1：水潭抽样（时间复杂度：O(n)；空间复杂度：O(1)）# 超时，该方法适用于大数据，内存存不下的业务情况def __init__(self, nums: List[int]):self.nums = numsdef pick(self, target: int) -> int:result, cnt = 0, 0for i, num in enumerate(self.nums):if num == target:cnt += 1if randrange(cnt) == 0:result = ireturn result

4.执行结果