Description给定一个可能重复的整数数组，随机输出给定目标数字的索引。您可以假设给定的目标编号必须存在于数组中。注意：数组大小可以很大。使用过多额外空间的解决方案将无法通过判断。示例：int[]nums=newint[]{1,2,3,3,3};Solutionsolution=newSolution(nums);//pick(3)应该随机返回索引2、3或4。每个索引应该有相等的返回概率。解决方案。pick(3);//pick(1)应该返回0。因为在数组中只有nums[0]等于1.solution.pick(1);描述给定一个可能包含重复元素的整数数组，要求随机输出给定数字的索引。您可以假设给定的数字必须存在于数组中。注意：数组大小可能非常大。使用过多额外空间的解决方案将无法通过测试。示例：int[]nums=newint[]{1,2,3,3,3};Solutionsolution=newSolution(nums);//pick(3)应返回索引2,3或4。每个索引应具有相等的返回概率。solution.pick(3);//pick(1)应该返回0。因为只有nums[0]等于1。solution.pick(1);来源：LeetCode链接：https://leetcode-cn.com/probl...版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。这道题的思路和382LinkedListRandomNode的解法类似。遍历给定的数组，统计当前满足条件的数n个，使用random函数随机生成一个1到n的数。如果选择n，则将当前数字替换为最终结果。#-*-编码：utf-8-*-#@作者：何锐#@创建日期：2019-08-3019:55:46#@最后修改者：何锐#@最后修改时间：2019-08-3020:17:06importheapqiimportrandomfromtypingimportListclass解决方案：def__init__(self,nums:List[int]):self.arrays=numsdefpick(self,target:int)->int:hep=[]fori,vinenumerate(self.arrays):ifv==target:#heap维护最小堆，会使用random.random()来比较#没有数字弹出的概率是同一个heapq.heappush(hep,(random.random(),i))_,index=heapq.heappop(hep)返回索引defpick2(self,target:int)->int:n,res=0,0forxinfilter(lambdax:x[1]==target,enumerate(self.arrays)):n+=1ifrandom.randint(1,n)==n:#求解思路同储水problemres=x[0]returnres源代码文件在这里。?
