题目

在选举中，第 i 张票是在时间为 times[i] 时投给 persons[i] 的。

现在，我们想要实现下面的查询函数： TopVotedCandidate.q(int t) 将返回在 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]

解释：时间为 3，票数分布情况是 [0]，编号为 0 的候选人领先。

时间为 12，票数分布情况是 [0,1,1]，编号为 1 的候选人领先。

时间为 25，票数分布情况是 [0,1,1,0,0,1]，编号为 1 的候选人领先（因为最近的投票结果是平局）。

在时间 15、24 和 8 处继续执行 3 个查询。

提示：1 <= persons.length = times.length <= 5000

0 <= persons[i] <= persons.length

times 是严格递增的数组，所有元素都在 [0, 10^9] 范围中。

每个测试用例最多调用 10000 次 TopVotedCandidate.q。

TopVotedCandidate.q(int t) 被调用时总是满足 t >= times[0]。

解题思路分析

1、二分查找；时间复杂度O(n)，空间复杂度O(n)

type TopVotedCandidate struct {
   result []int // 存放对应时间的候选人
   times  []int
}

func Constructor(persons []int, times []int) TopVotedCandidate {
   n := len(persons)
   arr := make([]int, n+1)
   maxCount := 0
   index := persons[0]
   res := make([]int, n)
   for i := 0; i < n; i++ {
      id := persons[i]
      arr[id]++
      if arr[id] >= maxCount {
         maxCount = arr[id]
         index = id
      }
      res[i] = index
   }
   return TopVotedCandidate{
      result: res,
      times:  times,
   }
}

func (this *TopVotedCandidate) Q(t int) int {
   left, right := 0, len(this.times)
   for left < right {
      mid := left + (right-left)/2
      if this.times[mid] == t {
         return this.result[mid]
      } else if this.times[mid] > t {
         right = mid
      } else {
         left = mid + 1
      }
   }
   return this.result[left-1]
}

2、二分查找；时间复杂度O(n)，空间复杂度O(n)

type TopVotedCandidate struct {
   result []int // 存放对应时间的候选人
   times  []int
}

func Constructor(persons []int, times []int) TopVotedCandidate {
   n := len(persons)
   arr := make([]int, n+1)
   maxCount := 0
   index := persons[0]
   res := make([]int, n)
   for i := 0; i < n; i++ {
      id := persons[i]
      arr[id]++
      if arr[id] >= maxCount {
         maxCount = arr[id]
         index = id
      }
      res[i] = index
   }
   return TopVotedCandidate{
      result: res,
      times:  times,
   }
}

func (this *TopVotedCandidate) Q(t int) int {
   left, right := 0, len(this.times)-1
   for left <= right {
      mid := left + (right-left)/2
      if this.times[mid] > t {
         right = mid - 1
      } else {
         left = mid + 1
      }
   }
   return this.result[left-1]
}

总结

Medium题目，设计类题目，提前计算好结果，然后使用二分查找