[LeetCode] 911. Online Election 在線選舉

In an election, the `i`-th vote was cast for `persons[i]` at time `times[i]`.

Now, we would like to implement the following query function: TopVotedCandidate.q(int t) will return the number of the person that was leading the election at time t.

Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.

Example 1:

Input: ["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]]
Output: [null,0,1,1,0,0,1]
Explanation:
At time 3, the votes are [0], and 0 is leading.
At time 12, the votes are [0,1,1], and 1 is leading.
At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
This continues for 3 more queries at time 15, 24, and 8.

Note:

1 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times is a strictly increasing array with all elements in [0, 10^9].
TopVotedCandidate.q is called at most 10000 times per test case.
TopVotedCandidate.q(int t) is always called with t >= times[0].

這道題是關于線上選舉的問題，這年頭感覺選舉都是得網絡者得天下啊，很多都是先在網上形成了一股潮流，比如美國的特朗普，英國的約翰遜，臺灣的韓國瑜等等，感覺各個都是社交媒體上的紅人，不走尋常路啊。扯遠了，拉回本題，其實剛開始博主看了幾遍題目，愣是沒理解題意，于是去論壇上逛逛，發現也有好多人不清楚，心里稍微舒坦點。這里給了兩個數組 persons 和 times，表示在某個時間點 times[i]，i這個人把選票投給了 persons[i]，現在有一個q函數，輸入時間點t，讓返回在時間點t時得票最多的人，當得票數相等時，返回最近得票的人。因為查詢需求的時間點是任意的，在某個查詢時間點可能并沒有投票發生，但需要知道當前的票王，當然最傻的辦法就是每次都從開頭統計到當前時間點，找出票王，但這種方法大概率會超時，正確的方法實際上是要在某個投票的時間點，都統計出當前的票王，然后在查詢的時候，查找剛好大于查詢時間點的下一個投票時間點，返回前一個時間點的票王即可，所以這里可以使用一個 TreeMap 來建立投票時間點和當前票王之間的映射。如何統計每個投票時間點的票王呢，可以使用一個 count 數組，其中 count[i] 就表示當前i獲得的票數，還需要一個變量 lead，表示當前的票王。現在就可以開始遍歷所有的投票了，對于每個投票，將票數加到 count 中對應的人身上，然后跟 lead 比較，若當前人的票數大于等于 lead 的票數，則 lead 更換為當前人，同時建立當前時間點和票王之間的映射。在查詢的時候，由于時間點是有序的，所以可以使用二分搜索法，由于使用的是 TreeMap，具有自動排序的功能，可以直接用 upper_bound 來查找第一個比t大的投票時間，然后再返回上一個投票時間點的票王即可，參見代碼如下：
解法一：

class TopVotedCandidate {
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        int n = persons.size(), lead = 0;
        vector<int> count(n + 1);
        for (int i = 0; i < n; ++i) {
        	if (++count[persons[i]] >= count[lead]) {
        		lead = persons[i];
        	}
        	m[times[i]] = lead;
        }
    }   
    int q(int t) {
        return (--m.upper_bound(t))->second;
    }
    
private:
	map<int, int> m;
};

我們也可以用 HashMap 來取代 TreeMap，但因為 HashMap 無法進行時間點的排序，不好使用二分搜索法了，所以就需要記錄投票時間數組 times，保存在一個私有變量中。在查詢函數中自己來寫二分搜索法，是博主之前的總結帖 [LeetCode Binary Search Summary 二分搜索法小結](http://www.rzrgm.cn/grandyang/p/6854825.html) 中的第三類，查找第一個大于目標值的數。由于要返回上一個投票時間點，所以要記得減1，參見代碼如下：
解法二：

class TopVotedCandidate {
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        int n = persons.size(), lead = 0;
        vector<int> count(n + 1);
        this->times = times;
        for (int i = 0; i < n; ++i) {
        	if (++count[persons[i]] >= count[lead]) {
        		lead = persons[i];
        	}
        	m[times[i]] = lead;
        }
    } 
    int q(int t) {
        int left = 0, right = times.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (times[mid] <= t) left = mid + 1;
            else right = mid;
        }
        return m[times[right - 1]];
    }
    
private:
	unordered_map<int, int> m;
	vector<int> times;
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/911

參考資料：

https://leetcode.com/problems/online-election/

https://leetcode.com/problems/online-election/discuss/173382/C%2B%2BJavaPython-Binary-Search-in-Times

https://leetcode.com/problems/online-election/discuss/191898/Anybody-has-a-magic-general-formula-for-Binary-Search

[LeetCode All in One 題目講解匯總(持續更新中...)](http://www.rzrgm.cn/grandyang/p/4606334.html)