Задача: 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 kotlin.random.Random
class Solution(n: Int, blacklist: IntArray) {
private val map = mutableMapOf<Int, Int>()
private val bound = n - blacklist.size
init {
val blackset = blacklist.toSet()
var whitelist = bound
for (b in blacklist) {
if (b < bound) {
while (blackset.contains(whitelist)) {
whitelist++
}
map[b] = whitelist
whitelist++
}
}
}
fun pick(): Int {
val r = Random.nextInt(bound)
return map.getOrDefault(r, r)
}
}
👉Новости 👉База вопросов