相关题目：
382. 链表随机节点
384. 打乱数组
398. 随机数索引
文章详解：
游戏中的随机抽样算法
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class RandListNode:
"""
382. 链表随机节点
https://leetcode.cn/problems/linked-list-random-node/
"""
def __init__(self, head: ListNode):
self.head = head
self.r = random.Random()
def getRandom(self) -> int:
i, res = 0, 0
p = self.head
# while 循环遍历链表
while p:
i += 1
# 生成一个 [0, i) 之间的整数
# 这个整数等于 0 的概率就是 1/i
if 0 == self.r.randint(0, i-1):
res = p.val
p = p.next
return res
class ShuffleArray:
"""
384. 打乱数组
https://leetcode.cn/problems/shuffle-an-array/
"""
def __init__(self, nums: List[int]):
self.nums = nums
def reset(self) -> List[int]:
return self.nums
def 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 copy
class 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, -1
for i in range(len(self.nums)):
if self.nums[i] != target:
continue
count += 1
if random.randint(1, count) == 1:
res = i
return res
from 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])