🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 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 для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение.
😎 Решение:
package main
import (
"math/rand"
"time"
)
type Solution struct {
mapping map[int]int
bound int
}
func Constructor(n int, blacklist []int) Solution {
mapping := make(map[int]int)
bound := n - len(blacklist)
blackset := make(map[int]struct{})
for _, b := range blacklist {
blackset[b] = struct{}{}
}
whitelist := bound
for _, b := range blacklist {
if b < bound {
for {
if _, exists := blackset[whitelist]; !exists {
break
}
whitelist++
}
mapping[b] = whitelist
whitelist++
}
}
return Solution{mapping: mapping, bound: bound}
}
func (this *Solution) Pick() int {
r := rand.Intn(this.bound)
if mapped, exists := this.mapping[r]; exists {
return mapped
}
return r
}
func main() {
rand.Seed(time.Now().UnixNano())
}
Ставь 👍 и забирай 📚 Базу знаний
