LC.P911[在线选举]

方法一：哈希表+二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class TopVotedCandidate {

    List<int[]> list = new ArrayList<>();

    public TopVotedCandidate(int[] persons, int[] times) {
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0; i < persons.length; ++i) {
            map.merge(persons[i], 1, Integer::sum);
            if (map.get(persons[i]) >= max) {
                max = map.get(persons[i]);
                list.add(new int[]{times[i], persons[i]});
            }
        }
    }

    public int q(int t) {
        int left = 0, right = list.size() - 1;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (list.get(mid)[0] <= t) left = mid;
            else right = mid - 1;
        }
        return list.get(right)[0] <= t ? list.get(right)[1] : 0;
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);
 */
  • 时间复杂度：$O(mlogn)$，其中$m$为查询次数，$n$为数组长度
  • 空间复杂度：$O(n)$