1.题目基本信息
1.1.题目描述
给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
优化你的算法，使它最小化调用语言 内置 随机函数的次数。
实现 Solution 类:
-
Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
-
int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数
1.2.题目地址
https://leetcode.cn/problems/random-pick-with-blacklist/description/
2.解题方法
2.1.解题思路
哈希表。记m=len(blacklist)，将[0,n-m)范围内的黑名单元素映射到[n-m,n)范围内的非黑名单元素，然后在[0,n-m)范围内进行随机选择，当选择到黑名单元素时，映射到[n-m,n)范围内的非黑名单元素
3.解题代码
python代码
class Solution:# 思路：哈希表。记m=len(blacklist)，将[0,n-m)范围内的黑名单元素映射到[n-m,n)范围内的非黑名单元素，然后在[0,n-m)范围内进行随机选择，当选择到黑名单元素时，映射到[n-m,n)范围内的非黑名单元素def __init__(self, n: int, blacklist: List[int]):m = len(blacklist)self.bound = n - mblackSet = set([i for i in blacklist if i >= self.bound]) # set(blacklist)self.map1 = {}# 将小于n-m的黑名单成员映射到大于等于n-m的非黑名单成员中w = n - mfor black in blacklist:if black < n - m:while w in blackSet:w += 1self.map1[black] = ww += 1# print(self.map1)def pick(self) -> int:x = randrange(self.bound)return self.map1.get(x, x)# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()
4.执行结果
)
