Medium

题目描述

给你两个整数数组 persons 和 times。在选举中，第 i 张票是在时刻 times[i] 投给 persons[i] 的。

对于发生在时刻 t 的每个查询，需要找出在时刻 t 时领先的候选人。在时刻 t 投的票也将被统计。如果有平局，最近投票的候选人（在平局的候选人中）获胜。

实现 TopVotedCandidate 类：

  • TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
  • int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。

示例 1：

输入：
["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]]
输出：
[null, 0, 1, 1, 0, 0, 1]

解释：
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3);  // 返回 0，在时刻 3，票数为 [0]，候选人 0 领先。
topVotedCandidate.q(12); // 返回 1，在时刻 12，票数为 [0,1,1]，候选人 1 领先。
topVotedCandidate.q(25); // 返回 1，在时刻 25，票数为 [0,1,1,0,0,1]，候选人 1 领先（平局时最近的票获胜）。
topVotedCandidate.q(15); // 返回 0
topVotedCandidate.q(24); // 返回 0  
topVotedCandidate.q(8);  // 返回 1

提示：

  • 1 <= persons.length <= 5000
  • times.length == persons.length
  • 0 <= persons[i] < persons.length
  • 0 <= times[i] <= 10^9
  • times 按严格递增顺序排列
  • times[0] <= t <= 10^9
  • 最多调用 q 10^4 次

解题思路

解题思路

这道题要求我们设计一个数据结构来高效处理在线选举查询。核心思路是预处理+二分查找。

分析过程：

  1. 预处理阶段：我们不能每次查询都重新统计票数，这会超时。关键观察是：每个时刻的领先者只在有新票投入时才可能改变。

  2. 状态维护：在构造函数中，我们按时间顺序处理每张票，维护每个候选人的票数，并记录每个时刻的领先者。当票数相等时，最近投票的候选人获胜。

  3. 查询优化：由于时间数组是严格递增的，我们可以使用二分查找来快速定位查询时刻 t 对应的状态。具体来说，找到最大的时间 times[i] <= t，此时的领先者就是答案。

算法步骤：

  • 构造时：遍历所有投票，维护票数统计和每个时刻的领先者
  • 查询时：二分查找定位时刻，返回对应的领先者

这种方法将查询的时间复杂度降低到 O(log n)，非常适合多次查询的场景。

代码实现

class TopVotedCandidate {
private:
    vector<int> times;
    vector<int> winners;
    
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        this->times = times;
        unordered_map<int, int> count;
        int leader = -1;
        int maxVotes = 0;
        
        for (int i = 0; i < persons.size(); i++) {
            count[persons[i]]++;
            if (count[persons[i]] >= maxVotes) {
                maxVotes = count[persons[i]];
                leader = persons[i];
            }
            winners.push_back(leader);
        }
    }
    
    int q(int t) {
        int idx = upper_bound(times.begin(), times.end(), t) - times.begin() - 1;
        return winners[idx];
    }
};

class TopVotedCandidate:
    def __init__(self, persons: List[int], times: List[int]):
        self.times = times
        self.winners = []
        count = {}
        leader = -1
        max_votes = 0
        
        for person in persons:
            count[person] = count.get(person, 0) + 1
            if count[person] >= max_votes:
                max_votes = count[person]
                leader = person
            self.winners.append(leader)
    
    def q(self, t: int) -> int:
        idx = bisect.bisect_right(self.times, t) - 1
        return self.winners[idx]

public class TopVotedCandidate {
    private int[] times;
    private int[] winners;
    
    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        this.winners = new int[persons.Length];
        Dictionary<int, int> count = new Dictionary<int, int>();
        int leader = -1;
        int maxVotes = 0;
        
        for (int i = 0; i < persons.Length; i++) {
            if (!count.ContainsKey(persons[i])) {
                count[persons[i]] = 0;
            }
            count[persons[i]]++;
            
            if (count[persons[i]] >= maxVotes) {
                maxVotes = count[persons[i]];
                leader = persons[i];
            }
            winners[i] = leader;
        }
    }
    
    public int Q(int t) {
        int left = 0, right = times.Length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (times[mid] <= t) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return winners[left];
    }
}

var TopVotedCandidate = function(persons, times) {
    this.times = times;
    this.winners = [];
    const count = new Map();
    let leader = -1;
    let maxVotes = 0;
    
    for (let i = 0; i < persons.length; i++) {
        count.set(persons[i], (count.get(persons[i]) || 0) + 1);
        if (count.get(persons[i]) >= maxVotes) {
            maxVotes = count.get(persons[i]);
            leader = persons[i];
        }
        this.winners.push(leader);
    }
};

TopVotedCandidate.prototype.q = function(t) {
    let left = 0, right = this.times.length - 1;
    while (left < right) {
        const mid = left + Math.floor((right - left + 1) / 2);
        if (this.times[mid] <= t) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return this.winners[left];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(n)O(n)
q 查询O(log n)O(1)

其中 n 是投票数量。构造时需要遍历所有投票并维护状态，查询时使用二分查找快速定位。

相关题目