{"id":4073,"date":"2018-09-25T08:32:30","date_gmt":"2018-09-25T15:32:30","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4073"},"modified":"2018-09-25T08:32:52","modified_gmt":"2018-09-25T15:32:52","slug":"leetcode-911-online-election","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-911-online-election\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 911. Online Election"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

n an election, the\u00a0i<\/code>-th\u00a0vote was cast for\u00a0persons[i]<\/code>\u00a0at time\u00a0times[i]<\/code>.<\/p>\n

Now, we would like to implement the following query function:\u00a0TopVotedCandidate.q(int t)<\/code>\u00a0will return the number of the person that was leading the election at time\u00a0t<\/code>.<\/p>\n

Votes cast at time\u00a0t<\/code>\u00a0will count towards our query.\u00a0 In the case of a tie, the most recent vote (among tied candidates) wins.<\/p>\n

\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>[\"TopVotedCandidate\",\"q\",\"q\",\"q\",\"q\",\"q\",\"q\"]<\/span>, [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]<\/span>\r\nOutput: <\/strong>[null,0,1,1,0,0,1]<\/span>\r\nExplanation: <\/strong>\r\nAt time 3, the votes are [0], and 0 is leading.\r\nAt time 12, the votes are [0,1,1], and 1 is leading.\r\nAt time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)\r\nThis continues for 3 more queries at time 15, 24, and 8.\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= persons.length = times.length <= 5000<\/code><\/li>\n
  2. 0 <= persons[i] <= persons.length<\/code><\/li>\n
  3. times<\/code>\u00a0is a strictly increasing array with all elements in\u00a0[0, 10^9]<\/code>.<\/li>\n
  4. TopVotedCandidate.q<\/code>\u00a0is called at most\u00a010000<\/code>\u00a0times per test case.<\/li>\n
  5. TopVotedCandidate.q(int t)<\/code>\u00a0is always called with\u00a0t >= times[0]<\/code>.<\/li>\n<\/ol>\n
    Solution: HashTable + Binary Search<\/strong><\/h1>\n
    Compute the leads for each t in times using a hash table.<\/p>\n
    binary search the upper bound of t, and return the lead of previous entry.<\/p>\n
    Time complexity: Constructor O(n), Query: O(logn)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\nclass TopVotedCandidate {\r\npublic:\r\n  TopVotedCandidate(vector<int> persons, vector<int> times) {\r\n    vector<int> votes(persons.size() + 1);\r\n    int last_lead = persons.front();\r\n    for (int i = 0; i < persons.size(); ++i) {\r\n      if (++votes[persons[i]] >= votes[last_lead])\r\n        last_lead = persons[i];      \r\n      leads_[times[i]] = last_lead;      \r\n    }\r\n  }\r\n\r\n  int q(int t) {\r\n    return prev(leads_.upper_bound(t))->second;\r\n  }\r\nprivate:\r\n  map<int, int> leads_; \/\/ time -> lead\r\n};<\/pre>\n<\/div><\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem n an election, the\u00a0i-th\u00a0vote was cast for\u00a0persons[i]\u00a0at time\u00a0times[i]. Now, we would like to implement the following query function:\u00a0TopVotedCandidate.q(int t)\u00a0will return the number of the…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149,70],"tags":[414,82,177,415,416],"class_list":["post-4073","post","type-post","status-publish","format-standard","hentry","category-binary-search","category-hashtable","tag-binary-seach","tag-hashtable","tag-medium","tag-online-query","tag-vote","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4073","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4073"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4073\/revisions"}],"predecessor-version":[{"id":4075,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4073\/revisions\/4075"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4073"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4073"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4073"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}