Скажем, у меня есть массив из N целых чисел со значением «0», и я хочу выбрать случайный элемент этого массива со значением «0» и присвоить ему значение «1».
Как мне сделать это эффективно?
Я придумал 2 решения, но они выглядят довольно неэффективно
Первое решение
int array[N] //init to 0s
int n //number of 1s we want to add to the array
int i = 0
while i < n
int a = random(0, N)
if array[a] == 0
array[a] = 1
i++
end if
end while
Это было бы крайне неэффективно для больших массивов из-за вероятности столкновения
Второй включает в себя список, содержащий все 0 оставшихся позиций, и мы выбираем случайное число между 0 и числом оставшихся 0 для поиска значения в списке, которое соответствует индексу в массиве. Это намного надежнее, чем первое решение, поскольку количество операций ограничено, но все же имеет сложность сценария в худшем случае N², если мы хотим полностью заполнить массив.
