题目

类型：design
image.png

解题思路

  • 根据题意，会在 times[i] 时刻为 persons[i]候选人增加一票。
  • 利用 times 数组严格递增，可以在处理 times 时（模拟加票过程），使用一个变量 val 来维护当前得票的最大数量，使用 list 来记录不同时刻点的候选人交替情况。
  • 起始时 val = 0，当出现票数大于等于 val 时，往 list 追加二元组记录 list[idx] = (times[i], persons[i])，并更新 val。

每个list[idx]代表了当前候选人list[idx][1] 的首次当选时刻为 list[idx][0]。
若 i = list[idx][0], j = list[idx + 1][0]，则意味着在时间段 [i, j) 内当选的候选人为list[idx][1]。
在查询时，只需要通过「二分」找到 list 中满足 list[i][0]<=t 的分割点 r（最大下标），取list[r][1]即是答案。

代码

  1. class TopVotedCandidate {
  2.     List<Integer> tops;
  3.     Map<Integer, Integer> voteCounts;
  4.     int[] times;
  6.     public TopVotedCandidate(int[] persons, int[] times) {
  7.         tops = new ArrayList<Integer>();
  8.         voteCounts = new HashMap<Integer, Integer>();
  9.         voteCounts.put(-1, -1);
  10.         int top = -1;
  11.         for (int i = 0; i < persons.length; ++i) {
  12.             int p = persons[i];
  13.             voteCounts.put(p, voteCounts.getOrDefault(p, 0) + 1);
  14.             if (voteCounts.get(p) >= voteCounts.get(top)) {
  15.                 top = p;
  16.             }
  17.             tops.add(top);
  18.         }
  19.         this.times = times;
  20.     }
  22.     public int q(int t) {
  23.         int l = 0, r = times.length - 1;
  24.         // 找到满足 times[l] <= t 的最大的 l
  25.         while (l < r) {
  26.             int m = l + (r - l + 1) / 2;
  27.             if (times[m] <= t) {
  28.                 l = m;
  29.             } else {
  30.                 r = m - 1;
  31.             }
  32.         }
  33.         return tops.get(l);
  34.     }
  35. }