How do I handle ties in the Online Election problem?

In case of a tie, the most recent vote among the tied candidates should be considered the leader. This can be implemented by keeping track of the last vote cast when the vote counts are the same.

Why is binary search used in this problem?

Binary search is used to quickly find the time range for a given query, optimizing the query response time from linear to logarithmic time.

What is the time complexity of this solution?

The time complexity for each query is O(log n), where n is the number of votes. This comes from using binary search to find the closest time to the query.

How can I optimize space complexity for this problem?

Space complexity can be optimized by storing only the necessary data, such as vote counts and leader history, while avoiding unnecessary duplication of data.

What are the main challenges of the Online Election problem?

The main challenges are efficiently handling ties in votes, optimizing query response times, and managing space complexity while tracking the leader history over time.

#911

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

在线选举

给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得…

数组哈希表二分查找设计

题目描述

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

对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。

在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。

实现 TopVotedCandidate 类：

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

示例：

输入：
["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 的候选人领先。（在平局的情况下，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⁹
times 是一个严格递增的有序数组
times[0] <= t <= 10⁹
每个测试用例最多调用 10⁴ 次 q

lightbulb

解题思路

方法一：二分查找

我们可以在初始化时，记录每个时刻的胜者，然后在查询时，使用二分查找找到小于等于 $t$ 的最大时刻，返回该时刻的胜者。

初始化时，我们使用一个计数器 $cnt$ 记录每个候选人的票数，用一个变量 $cur$ 记录当前领先的候选人。然后遍历每个时刻，更新 $cnt$ 和 $cur$ ，并记录每个时刻的胜者。

查询时，我们使用二分查找找到小于等于 $t$ 的最大时刻，返回该时刻的胜者。

时间复杂度方面，初始化时，我们需要 $O(n)$ 的时间，查询时，我们需要 $O(\log n)$ 的时间。空间复杂度为 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        cnt = Counter()
        self.times = times
        self.wins = []
        cur = 0
        for p in persons:
            cnt[p] += 1
            if cnt[cur] <= cnt[p]:
                cur = p
            self.wins.append(cur)

    def q(self, t: int) -> int:
        i = bisect_right(self.times, t) - 1
        return self.wins[i]


# Your TopVotedCandidate object will be instantiated and called as such:
# obj = TopVotedCandidate(persons, times)
# param_1 = obj.q(t)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for an implementation that efficiently handles multiple queries with binary search and constant-time query results.
question_mark
The candidate should correctly handle tie-breaking scenarios where the latest vote counts.
question_mark
Check if the candidate optimizes the space complexity by storing only necessary data (votes and leader history).

warning

常见陷阱

外企场景

error
Not handling ties correctly by returning the most recent vote in case of equal votes.
error
Inefficient query response times, especially when failing to use binary search on the `times` array.
error
Not optimizing the space complexity, potentially storing unnecessary data or failing to use a hash map for vote counts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to support multiple candidates in the `persons` array instead of just two.
arrow_right_alt
Allow for multiple queries at the same time and return the leaders for all queries in a single batch.
arrow_right_alt
Alter the `times` array to include non-integer values (e.g., floating point), testing edge cases with time formatting.

help

常见问题

外企场景

继续练习

#1146 快照数组 #888 公平的糖果交换 #981 基于时间的键值存储