网站国外推广,网站开发设计流程文档,购物网站多少钱,装饰公司网站模板下载相关题目#xff1a; 382. 链表随机节点 384. 打乱数组 398. 随机数索引
文章详解#xff1a; 游戏中的随机抽样算法
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass RandListNode:382. 链表随机节点https://lee…相关题目 382. 链表随机节点 384. 打乱数组 398. 随机数索引
文章详解 游戏中的随机抽样算法
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextclass RandListNode:382. 链表随机节点https://leetcode.cn/problems/linked-list-random-node/def __init__(self, head: ListNode):self.head headself.r random.Random()def getRandom(self) - int:i, res 0, 0p self.head# while 循环遍历链表while p:i 1# 生成一个 [0, i) 之间的整数# 这个整数等于 0 的概率就是 1/iif 0 self.r.randint(0, i-1):res p.valp p.nextreturn resclass ShuffleArray:384. 打乱数组https://leetcode.cn/problems/shuffle-an-array/def __init__(self, nums: List[int]):self.nums numsdef reset(self) - List[int]:return self.numsdef shuffle(self) - List[int]:copy self.nums.copy()n len(self.nums)for i in range(n):# 生成一个 [i, n-1] 区间内的随机数r i random.randint(0, n-i-1)# 交换 nums[i] 和 nums[r]copy[i], copy[r] copy[r], copy[i]return copyclass RandomIndex:398. 随机数索引https://leetcode.cn/problems/random-pick-index/description/def __init__(self, nums: List[int]):self.nums nums# self.rand random.Random()def pick(self, target: int) - int:count, res 0, -1for i in range(len(self.nums)):if self.nums[i] ! target:continuecount 1if random.randint(1, count) 1:res ireturn resfrom collections import defaultdict
from random import choice
class RandomIndex2:398. 随机数索引def __init__(self, nums: List[int]):self.pos defaultdict(list)for i, num in enumerate(nums):self.pos[num].append(i)def pick(self, target: int) - int:return choice(self.pos[target])
