刷题记录第五十一天-黑名单中的随机数

2023-12-20 01:30:56

题目描述如下:
给定一个整数n和一个整数黑名单balcklist,目标是写一个随机函数,随机从(0,n-1)中选择一个不属于黑名单里的数,且每个数被取得的概率相同。
思路如下:

  1. 假设用rand()函数从[ 0,n-balcklist.size() )中随机取一个数,那么取到的数可能是黑名单里的数。
  2. 假设黑名单里有k个数在[0,size())里,那么就有k个不属于黑名单的数在[size,n-1)里。
  3. 我们只需要用一个map,将[0,size())中属于黑名单的数一一映射成[size,n-1)中非黑名单数即可。
  4. 最后,利用rand()%size得到的数如果属于黑名单就返回map映射,否则就返回这个数
class Solution {
public:
    int size;
    unordered_map<int,int> map;
    Solution(int n, vector<int>& blacklist) {
        for(int i:blacklist){
            map[i]=1;
        }
        size = n-blacklist.size();
        int last = n-1;
        for(int num:blacklist){
            if(num>=size)
                continue;
            while(map.count(last)!=0){
                last--;
            }
            map[num]=last;
            last--;
        }
    }
    
    int pick() {
        int num=rand()%size;
        if(map.count(num)!=0){
            return map[num];
        }
        return num;
    }
};

文章来源:https://blog.csdn.net/weixin_45850570/article/details/135095900
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。