Задача: 911. Online Election
Сложность: medium

Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.

Пример:
Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

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

1⃣Использовать два массива для хранения лиц и времени голосования.

2⃣Поддерживать текущий счет для каждого кандидата и текущего лидера на момент времени.

3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени.

😎 Решение:
class TopVotedCandidate {
private $times;
private $leaders;

function __construct($persons, $times) {
$this->times = $times;
$this->leaders = [];
$counts = [];
$leader = -1;

foreach ($persons as $person) {
if (!isset($counts[$person])) {
$counts[$person] = 0;
}
$counts[$person]++;
if (!isset($counts[$leader]) || $counts[$person] >= $counts[$leader]) {
$leader = $person;
}
$this->leaders[] = $leader;
}
}

function q($t) {
$left = 0;
$right = count($this->times) - 1;
while ($left < $right) {
$mid = intdiv($left + $right + 1, 2);
if ($this->times[$mid] leaders[$left];
}
}

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