Сложность: medium
Дан односвязный список, вернуть значение случайного узла из списка. Каждый узел должен иметь одинаковую вероятность быть выбранным.
Реализуйте класс Solution:
Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.
Пример:
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]
Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
👨💻 Алгоритм:
1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.
2⃣В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже.
3⃣Реализуйте функцию getRandom(), которая будет выбирать случайный элемент из массива, созданного на первом этапе.
😎 Решение:
class ListNode {
public $val;
public $next;
public function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class Solution {
private $range = array();
public function __construct($head) {
while ($head !== null) {
$this->range[] = $head->val;
$head = $head->next;
}
}
public function getRandom() {
$pick = rand(0, count($this->range) - 1);
return $this->range[$pick];
}
}
?>Ставь 👍 и забирай 📚 Базу знаний