当前位置:网站首页>Force buckle 710 Random numbers in the blacklist
Force buckle 710 Random numbers in the blacklist
2022-07-01 23:02:00 【Three watch ghost】
Title source :https://leetcode.cn/problems/random-pick-with-blacklist/
General meaning :
Given a range of numbers n, An array of blacklists , Design a class return 0 To n - 1 Between random numbers that are not in the blacklist , It is required that the probability of each number being returned should be equal
Ideas
Set the blacklist array length to m, Then the number of returned numbers is n - m individual
So you can set the random number bound by n - m
- If the number in the blacklist is greater than or equal to bound, Then you don't have to do anything
- If the number in the blacklist is less than bound, You can use a hash table to map it to [bound, n - 1] in . In this way, the blacklist generated by the random number generator is less than bound The number of hours , Directly map to another number
Code :
public class Pick {
// The mapping blacklist is less than bound Number of numbers
Map<Integer, Integer> map;
int bound;
Random random;
public Pick(int n, int[] blacklist) {
map = new HashMap<>();
int m = blacklist.length;
// initialization bound
bound = n - m;
random = new Random();
// Save the hash table of blacklist numbers
Set<Integer> blackSet = new HashSet<>();
for (int num : blacklist) {
if (num >= bound) {
blackSet.add(num);
}
}
// Mapping index
int idx = bound;
// Traverse the blacklist
for (int num : blacklist) {
// If the blacklist number is less than bound, Map it to [bound, n - 1] The number that is not in the blacklist and has not been mapped
if (num < bound) {
// If the current number to be mapped is in the blacklist , Indexes +1
while (blackSet.contains(idx)) {
idx++;
}
map.put(num, idx++);
}
}
}
public int pick() {
// Generate random number
int x = random.nextInt(bound);
// Return random number , If the random number is map in , Returns the number of its mapping
return map.getOrDefault(x, x);
}
}
边栏推荐
- shell 自定义函数
- 正则系列之组和范围(Groups and Ranges)
- Armbain系统根分区空间不足处理
- window10安装wsl(一)(WslRegisterDistribution ERROR)
- Copy ‘XXXX‘ to effectively final temp variable
- cvpr2022 human pose estiamtion
- el-input文本域字数限制,超过显示变红并禁止输入
- Talk about what parameters ZABBIX monitors
- Congratulations on the release of friends' new book (send welfare)
- Vsphere+ and vsan+ are coming! VMware hybrid cloud focus: native, fast migration, mixed load
猜你喜欢
【嵌入式系统课设】单个按键控制LED灯
“信任机器”为发展赋能
正则系列之量词(Quantifiers)
使用 EMQX Cloud 实现物联网设备一机一密验证
台积电全球员工薪酬中位数约46万,CEO约899万;苹果上调日本的 iPhone 售价 ;Vim 9.0 发布|极客头条
数字化转型道阻且长,如何迈好关键的第一步
The last packet sent successfully to the server was 0 milliseconds ago. The driver has not received
Quantifiers of regular series
思科考试--路由的概念和配置考试
I graduated from college in 14 years and changed to software testing in 3 months. My monthly salary was 13.5k. At the age of 32, I finally found the right direction
随机推荐
[MySQL] index classification
Genicam gentl standard ver1.5 (4) Chapter 5 acquisition engine
Share some feelings of a programmer who has experienced layoffs twice a year
转--利用C语言中的setjmp和longjmp,来实现异常捕获和协程
转--深入LUA脚本语言,让你彻底明白调试原理
Chen Tianqi's machine learning compilation course (free)
毕业季,既是告别,也是新的开始
Cloud Vulnerability Global Database
Fiori 应用通过 Adaptation Project 的增强方式分享
Sogou wechat app reverse (II) so layer
Detailed explanation of common configurations in redis configuration file [easy to understand]
轉載csdn文章操作
聊一聊Zabbix都监控哪些参数
The principle, testing and Countermeasures of malicious software reverse closing EDR
Quantifiers of regular series
思科--高可用和高可靠网络考试
Turn -- use setjmp and longjmp in C language to realize exception capture and collaboration
Electron学习(三)之简单交互操作
Flink SQL command line connection yarn
Mysql 5.7 实现 rank 排名