Задача: 710. Random Pick with Blacklist
Сложность: hard

Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список.

Пример:

Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]

👨‍💻 Алгоритм:

1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список.

2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка.

3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение.

😎 Решение:

class Solution {
public:
    Solution(int n, std::vector<int>& blacklist) {
        bound = n - blacklist.size();
        std::unordered_set<int> blackset(blacklist.begin(), blacklist.end());
        int whitelist = bound;
        for (int b : blacklist) {
            if (b < bound) {
                while (blackset.count(whitelist)) {
                    whitelist++;
                }
                map[b] = whitelist;
                whitelist++;
            }
        }
    }
    
    int pick() {
        int r = rand() % bound;
        return map.count(r) ? map[r] : r;
    }
    
private:
    std::unordered_map<int, int> map;
    int bound;
};

Ставь 👍 и забирай 📚 Базу знаний