Сложность: 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 {
public:
TopVotedCandidate(vector<int>& persons, vector<int>& times) {
this->times = times;
unordered_map<int, int> counts;
int leader = -1;
for (int person : persons) {
counts[person]++;
if (counts[person] >= counts[leader]) {
leader = person;
}
leaders.push_back(leader);
}
}
int q(int t) {
auto it = upper_bound(times.begin(), times.end(), t);
return leaders[it - times.begin() - 1];
}
private:
vector<int> times;
vector<int> leaders;
};Ставь 👍 и забирай 📚 Базу знаний