JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-09-28
目录

黑名单中的随机数Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法,从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法,使它最小化调用语言 内置 随机函数的次数。

实现 Solution 类:

  • Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
  • int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数

示例 1:

输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]

解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0,任何[0,1,4,6]的整数都可以。注意,对于每一个pick的调用,
                 // 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4

提示:

  • 1 <= n <= 109
  • 0 <= blacklist.length <= min(105, n - 1)
  • 0 <= blacklist[i] < n
  • blacklist 中所有值都 不同
  • pick 最多被调用 2 * 104 次

# 思路

int whiteEnd;
Random random;
HashMap<Integer, Integer> table;

# 解法


class Solution {

    int whiteEnd;
    Random random;
    HashMap<Integer, Integer> table;

    public Solution(int n, int[] blacklist) {
        //init
        HashSet<Integer> blackset = new HashSet<>();
        table = new HashMap<>();
        random = new Random();

        //将[0, n - 1] 划分成两个区间 [0, whileEnd) [whileEnd, n - 1] 前者是认为是白名单区间,后者认为是黑名单区间
        whiteEnd = n - blacklist.length;
        //对给定的【黑名单数组】遍历可知, 找出【黑名单】散布在黑名单区间[whileEnd, n - 1]中的记录,收集到blackset, 
        for (int num : blacklist) {
            if (num >= whiteEnd) blackset.add(num);
        }
        //黑名单区间[whileEnd, n - 1]中存在的白名单
        List<Integer> whites = new ArrayList<>();
        //黑名单区间中如果不是黑名单,那么就是白名单了,收集白名单
        for (int i = whiteEnd; i < n; i++) {
            if (!blackset.contains(i)) whites.add(i);
        }
        //将白名单区间中的黑名单 和 黑名单区间中的白名单 构建映射
        int index = 0;
        for (int b : blacklist) {
            if (b < whiteEnd) {
                table.put(b, whites.get(index++));
            }
        }
    }
    
    public int pick() {
        int ran = random.nextInt(whiteEnd);
        if (table.containsKey(ran)) {
            return table.get(ran);
        }
        return ran;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(n, blacklist);
 * int param_1 = obj.pick();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1637. 两点之间不包含任何点的最宽垂直区域 Java
06-26
02
1636. 按照频率将数组升序排序 Java
06-26
03
1638. 统计只差一个字符的子串数目 Java
06-26
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式