Java | LeetCode

#hard
Задача: 710. Random Pick with Blacklist

Вам дано целое число 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 для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение.

😎

Решение:

import java.util.*;

public class Solution {
    private Map<Integer, Integer> map;
    private int bound;

    public Solution(int n, int[] blacklist) {
        map = new HashMap<>();
        bound = n - blacklist.length;
        Set<Integer> blackset = new HashSet<>();
        for (int b : blacklist) {
            blackset.add(b);
        }
        int whitelist = bound;
        for (int b : blacklist) {
            if (b < bound) {
                while (blackset.contains(whitelist)) {
                    whitelist++;
                }
                map.put(b, whitelist);
                whitelist++;
            }
        }
    }

    public int pick() {
        int r = (int) (Math.random() * bound);
        return map.getOrDefault(r, r);
    }
}

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

Please open Telegram to view this post