• 710. 黑名单中的随机数


    给定一个整数 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 次

    /保证0-wsize 都是白名单,如果里面有黑名单的映射到wsize-n的白名单中
    //遍历两次黑名单,

    class Solution {
    public:
        Solution(int n, vector& blacklist) {
            sort(blacklist.begin(), blacklist.end());
            total = n;
            bSize = blacklist.size();
            wSize = total - bSize;
            for (auto it : blacklist)
            {
                if (it >= wSize)
                {
                    bMap[it] = it;
                }
            }
            int index = wSize;
            while (bMap.count(index) > 0)
            {
                index++;
            }
            for (int i = 0; i < blacklist.size();i++)
            {
                if (blacklist[i] >= wSize)
                {
                    break;
                }
                wMap[blacklist[i]] = index;
                index++;
                while (bMap.count(index) > 0)
                {
                    index++;
                }
            }    
        }

        int pick() 
        {
            int num = rand() % wSize;
            if (wMap.size() >0 )
            {
                num = wMap.count(num)>0 ? wMap[num] : num;
            }
            return num;
        }
    private:
        mapbMap;
        mapwMap;
        int bSize;
        int total;
        int wSize;
    };

     

  • 相关阅读:
    【SpringBoot集成Redis + Session持久化存储到Redis】
    【回眸】写篇博客记录一下嵌入式软件实习萌新的具体工作之使用AURIX Development Studio编译
    什么是网络攻击?
    后端配置(宝塔):SSH终端设置
    Qt-FFmpeg开发-视频播放(3)
    如何分析判断一篇文章是不是chatgpt写的
    onebound电商API接口商品数据采集平台:让数据成为生产力!
    聚观早报 | 荣耀Play8T上市;阿芙“超级品牌日”上线
    微前端三:qiankun 协作开发和上线部署
    数据结构(八)排序
  • 原文地址:https://blog.csdn.net/yinhua405/article/details/127681656