力扣每日一题之在线选举

发表于

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

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

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

你的任务：实现ToVotedCandidate类：

  • 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]

解释：

  • 时刻为0时第0张票投给了0号；
    • 时刻为3时此时都没有票，所以返回0；
  • 时刻为5时第1张票投给了1号；
    • 时刻为8时此时票数分布是[0, 1]，因为1是最近获得选票的候选人，因此返回1；
  • 时刻为10时第2张票投给了1号；
    • 时刻为12时此时票数分布是[0, 1, 1]，此时返回1；
  • 时刻为15时第3张票投给了0号；
  • 时刻为20时第4张票投给了0号；
  • 时刻为25时第4张票投给了1号；
    • 时刻为25时此时票数分布为[0, 1, 1, 0, 0, 1]，又因为1是最近获得票的候选人，因此返回1；
  • 时刻为30时第5张票投给了0号。

方法一：预计算+二分查找

记persons的长度为N。我们对输入进行预计算，用一个长度为N的数组tops记录各时间段得票数领先的候选人。具体来说，tops[i]表示 \[ \begin{cases} times[i]≤t<times[i+1],& 0≤i<N−1 \\ t≥times[i],& i=N-1 \end{cases} \] 的时间段的领先的候选人，这样的预计算可以通过对persons在time上的计数完成。

具体实现方法是：

  • 用一个哈希表voteCounts记录不同的候选人的得票数，用一个变量top表示当前领先的候选人。按时间从小到大遍历persons和times，并更新voteCounts和top，把top放入tops。遍历结束后，我们可以得到一个长度为N的tops，表示各个时间段的票领先的候选人。
  • 每次查询时，我们在times中找出不大于t且离t最近的元素的下标，这部操作可以通过二分查找完成。到tops索引相同的下标即可返回结果。

顺序查找

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
type TopVotedCandidate struct {
	tops        []int
	times       []int
}

func Constructor(persons, times []int) TopVotedCandidate {
	tops := []int{}
	top := -1
	voteCounts := map[int]int{-1: -1}
	for _, p := range persons {
		voteCounts[p]++
		if voteCounts[p] >= voteCounts[top] {
			top = p // 记录上一个p
		}
		tops = append(tops, top)
	}
	return TopVotedCandidate{tops, times}
}

func (t *TopVotedCandidate) Q(i int) int {
	// 顺序查找
	gap := 10000000
	ret := 0
	for index, value := range t.times {
		if i-value < gap && i >= value {
			gap = i - value
			ret = index
		}
	}
	fmt.Println(t.tops[ret])
	return t.tops[ret]
}

手写二分查找

  • 区间[left,right], left <= right，i > mid(left=mid+1)，i<mid(right=mid-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (t *TopVotedCandidate) Q(i int) int {
	// 二分查找
	mid := 0
	left := 0
	right := len(t.times) - 1
	for left <= right {
		mid = left + (right-left)/2
		if i > t.times[mid] {
			left = mid + 1
		} else if i < t.times[mid] {
			right = mid - 1
		} else {
			return t.tops[mid]
		}
	}
	return t.tops[right]
}

库函数二分查找

1
2
3
func (c *TopVotedCandidate) Q(t int) int {
    return c.tops[sort.SearchInts(c.times, t+1)-1]
}