911.在线选举

链接：911.在线选举
难度：Medium
标签：设计、数组、哈希表、二分查找
简介：给你两个整数数组 persons 和 times 。在选举中，第  i  张票是在时刻为  times[i]  时投给候选人 persons[i]  的。对于发生在时刻 t 的每个查询，需要找出在  t 时刻在选举中领先的候选人的编号。

题解 1 - typescript

• 编辑时间：2021-12-11
• 执行用时：292ms
• 内存消耗：51.5MB
• 编程语言：typescript
• 解法介绍：初始化时记录每个时刻的获胜人数，遍历用二分。

class TopVotedCandidate {
  arr: number[] = [];
  constructor(persons: number[], private times: number[]) {
    const n = persons.length;
    const temp = new Array(n).fill(0);
    let max = 0;
    for (const person of persons) {
      if (++temp[person] >= temp[max]) max = person;
      this.arr.push(max);
    }
  }
  q(t: number): number {
    let l = 0;
    let r = this.times.length - 1;
    while (l < r) {
      const mid = (l + r + 1) >> 1;
      if (this.times[mid] <= t) l = mid;
      else r = mid - 1;
    }
    return this.arr[l];
  }
}