Задача: 528. Random Pick with Weight
Сложность: medium

Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i.
Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w).
Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%).

Пример:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

👨‍💻 Алгоритм:

1⃣Инициализация и предобработка весов:
В конструкторе создайте массив накопительных сумм prefixSums, где каждая позиция будет содержать сумму всех предыдущих весов до текущего индекса включительно.
Также в конструкторе сохраните общую сумму весов totalSum.

2⃣Генерация случайного числа и выбор индекса:
В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum.
Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу.

3⃣Возврат результата:
Верните найденный индекс.

😎 Решение:

class Solution {
    private $prefixSums;
    private $totalSum;

    /**
     * @param Integer[] $w
     */
    function __construct($w) {
        $this->prefixSums = array_fill(0, count($w), 0);
        $prefixSum = 0;
        for ($i = 0; $i < count($w); $i++) {
            $prefixSum += $w[$i];
            $this->prefixSums[$i] = $prefixSum;
        }
        $this->totalSum = $prefixSum;
    }

    /**
     * @return Integer
     */
    function pickIndex() {
        $target = $this->totalSum * (mt_rand() / mt_getrandmax());
        for ($i = 0; $i < count($this->prefixSums); $i++) {
            if ($target < $this->prefixSums[$i]) {
                return $i;
            }
        }
        return count($this->prefixSums) - 1;
    }
}

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