leetcode每日一题 911在线选举

leetcode每日一题 911在线选举

思路：主要是预处理，记录一个当前时刻最大值，遍历times数组，得到每个时刻的领先人，方法是记录一个当前的最大值，比较当前时刻得票人和之前领先人的得票数就行了，最后二分查找要求的时刻之前的那个投票时刻的领先人。

class TopVotedCandidate {
public:
    int ticket[5005];  //票数
    int late[5005];    //下标为i的人最近一次得票的时间。
    vector  an;
    vector  m_times;
    int mmax,nowmax;
    int mi,nowi;
    int l,l2;
    TopVotedCandidate(vector& persons, vector& times) {
        memset(ticket,0,sizeof(ticket));
        l = times.size();
        m_times = times;
        l2 = persons.size();
        mmax = nowmax = -1;
        for(int i = 0; i < l; i++){
            ticket[persons[i]]++;
            late[persons[i]] = times[i];
            nowmax = ticket[persons[i]];
            nowi = persons[i];
            if(nowmax > mmax || (nowmax == mmax && late[nowi] > late[mi])){
                mmax = nowmax;
                mi = nowi;
            }
        //    cout << mi << endl;
            an.push_back(mi);
        }
    }
    
    int q(int t) {
        if(t < m_times[0]){
            return -1;
        }else if(t > m_times[l-1]){
            return an[l-1];
        }else{
            int x = lower_bound(m_times.begin(), m_times.end(), t) - m_times.begin();
            if(m_times[x] != t){
                x--;
            }
        //    cout << t << " " << x  << endl;
            return an[x];
        }
    }
};

![](https://img-blog.csdnimg.cn/b046879bdb85477ab244b0bf0055a6e0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,