游戏中的随机抽样算法

相关题目：
382. 链表随机节点
384. 打乱数组
398. 随机数索引

文章详解：
游戏中的随机抽样算法

class ListNode:def __init__(self, val=0, next=None):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])