710.黑名单中的随机数

链接：710.黑名单中的随机数
难度：Hard
标签：数组、哈希表、数学、二分查找、排序、随机化
简介：给定一个整数 n 和一个 无重复 黑名单整数数组  blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个   未加入   黑名单  blacklist  的整数。任何在上述范围内且不在黑名单  blacklist  中的整数都应该有 同等的可能性 被返回。

题解 1 - cpp

• 编辑时间：2022-06-26
• 执行用时：112ms
• 内存消耗：68.6MB
• 编程语言：cpp
• 解法介绍：修改随机范围把范围内不可能取到的值映射出去。

class Solution {
   public:
    int n;
    unordered_map<int, int> m;
    Solution(int n, vector<int> &blacklist) {
        srand(time(0));
        int size = blacklist.size(), nextN = n - size;
        unordered_set<int> s;
        for (auto &num : blacklist) {
            if (num >= nextN) s.emplace(num);
        }
        int i = nextN;
        for (auto &num : blacklist) {
            if (num >= nextN) continue;
            while (s.count(i)) i++;
            m[num] = i++;
        }
        this->n = nextN;
    }
    int pick() {
        int num = floor(random() % n);
        return m.count(num) ? m[num] : num;
    }
};