Задача: 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] <= $t) {
                $left = $mid;
            } else {
                $right = $mid - 1;
            }
        }
        return $this->leaders[$left];
    }
}

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