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.執行結果
)
