Сгенерируйте слайс из n уникальных случайных целых
Реализуйте uniqRandn(n), возвращающую слайс из n различных случайных целых. Ни одно значение не должно повторяться. Подсказка: используйте множество, отбрасывая дубликаты по мере заполнения результата.
func uniqRandn(n int) []int {
// ваш код здесь
return nil
}Допишите реализацию.
Держите map[int]struct{} как множество и слайс-результат. Цикл, пока len(res) == n: берите rand.Int(), и если он уже в множестве, пропускайте через continue; иначе добавляйте его и записывайте в множество. Значение struct{} не занимает памяти, а множество даёт проверку дубликата за O(1), поэтому ожидаемая стоимость близка к O(n) при большом диапазоне.
- ✗Пропускать проверку дубликатов, считая, что
rand.Int()не сталкивается - ✗Сортировать-затем-дедуп, что может дать меньше
nзначений - ✗Использовать линейный скан слайса вместо map для поиска за O(1)
- →Почему этот цикл может долго крутиться, если диапазон случайных мал, а
nблизко к его размеру? - →Как перемешивание
0..mсгенерируетnуникальных значений без отбрасывания?
Решение
map[int]struct{} — идиоматичное множество в Go: struct{} занимает ноль байт.
func uniqRandn(n int) []int {
res := make([]int, 0, n)
seen := make(map[int]struct{}, n)
for len(res) < n {
val := rand.Int()
if _, ok := seen[val]; ok {
continue // дубликат — тянем заново
}
res = append(res, val)
seen[val] = struct{}{}
}
return res
}Проверка seen[val] — O(1). Пока диапазон rand.Int() огромен, коллизии редки и цикл делает ~n итераций. Полагаться на «коллизий не бывает» нельзя — дедуп обязателен для гарантии уникальности.
⚠️ Если диапазон случайных мал и n близко к его размеру, цикл с отбрасыванием может крутиться очень долго; тогда лучше перемешать 0..m и взять первые n.
