911. 在线选举
给你两个整数数组 persons 和 times 。在选举中,第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。
对于发生在时刻 t 的每个查询,需要找出在 t 时刻在选举中领先的候选人的编号。
在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下,最近获得投票的候选人将会获胜。
实现 TopVotedCandidate 类:
TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
int q(int t) 根据前面描述的规则,返回在时刻 t 在选举中领先的候选人的编号。
这题做了两个小时然后发现极端用例超时了
把我整麻了
以下是我的超时错误代码
我的思路其实差不多,二分法查找t所对应的位置
然后哈希表来存储键值,设定一个max作为比较标准
最后保留最大值的索引直接输出候选人
但是不知道为啥最后在极端用例上超时gg了
public class TopVotedCandidate { public int[] persons; public int[] times; public TopVotedCandidate(int[] persons, int[] times) { this.persons = persons; this.times = times; } public int Q(int t) { int left = 0; int right = times.Length - 1; int ans = 0; while (left < right) { if(t >= times[right]) { ans = Count(right); break; } int mid = (right - left) / 2 + left; if (t == times[mid]) { ans = Count(mid); break; } else if (t < times[mid]) { right = mid; if (right - left == 1) { if(t > times[left] && t<times[right]) { ans = Count(left); break; } } } else if (t > times[mid]) { left = mid; if (right - left == 1) { if (t > times[left] && t < times[right]) { ans = Count(left); break; } } } } return ans; } public int Count(int number) { Hashtable voted = new Hashtable(); int max = 0; for (int i = 0; i <= number; i++) { if (voted.Contains(persons[i])) { int temp = (int)voted[persons[i]]; temp++; voted[persons[i]] = temp; if ((int)voted[persons[i]] > (int)voted[persons[max]]) { max = i; } else if((int)voted[persons[i]] == (int)voted[persons[max]]) { if(max < i) { max = i; } } } else { voted.Add(persons[i], 1); if ((int)voted[persons[i]] > (int)voted[persons[max]]) { max = i; } else if ((int)voted[persons[i]] == (int)voted[persons[max]]) { if (max < i) { max = i; } } } } return persons[max]; } }
挂一下官方的思路吧
public class TopVotedCandidate { IList<int> tops; Dictionary<int, int> voteCounts; int[] times; public TopVotedCandidate(int[] persons, int[] times) { tops = new List<int>(); voteCounts = new Dictionary<int, int>(); voteCounts.Add(-1, -1); int top = -1; for (int i = 0; i < persons.Length; ++i) { int p = persons[i]; if (!voteCounts.ContainsKey(p)) { voteCounts.Add(p, 0); } else { ++voteCounts[p]; } if (voteCounts[p] >= voteCounts[top]) { top = p; } tops.Add(top); } this.times = times; } public int Q(int t) { int l = 0, r = times.Length - 1; // 找到满足 times[l] <= t 的最大的 l while (l < r) { int m = l + (r - l + 1) / 2; if (times[m] <= t) { l = m; } else { r = m - 1; } } return tops[l]; } }