每日一题——911. 在线选举

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];
    }
}