LeetCode 911. 在线选举题目样例图解

左手的ㄟ右手 2022-02-05 12:45 102阅读 0赞

在选举中，第 i 张票是在时间为 times\[i\] 时投给 persons\[i\] 的。现在，我们想要实现下面的查询函数： TopVotedCandidate.q(int t) 将返回在 t 时刻主导选举的候选人的编号。在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。

示例：

> 输入：\[“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\]\]  
> 输出：\[null,0,1,1,0,0,1\]  
> 解释：  
> 时间为 3，票数分布情况是 \[0\]，编号为 0 的候选人领先。  
> 时间为 12，票数分布情况是 \[0,1,1\]，编号为 1 的候选人领先。  
> 时间为 25，票数分布情况是 \[0,1,1,0,0,1\]，编号为 1 的候选人领先（因为最近的投票结果是平局）。  
> 在时间 15、24 和 8 处继续执行 3 个查询。

样例图解，主要是两个数组，以及每次要查询的 t 值。按照 t 的顺序输出即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1h1X0pMMTk5Nw_size_16_color_FFFFFF_t_70]

Java 解法，通过 96/97，真的吐槽时间。

class TopVotedCandidate { 
    
        private int[] persons;
        private int[] times;
        // 将每一次投票的获胜者保存下来，key为时间，value为候选人
        private HashMap<Integer, Integer> winner = new HashMap<>();
        
        public TopVotedCandidate(int[] persons, int[] times) { 
            this.persons = persons;  // 选票选择的候选人
            this.times = times;  // 选票投出的时间
    
            int[] votes = new int[persons.length + 1]; // 记录每个候选人的得票 
            int currentWinner = persons[0];  // 记录第i次投票获胜的候选人
                
            for(int i = 0; i < times.length; i++){ 
                votes[persons[i]] ++;
                // 票投给了其他人，考察是否需要改变获胜者
                if(persons[i] != currentWinner) { 
                    if(votes[persons[i]] >= votes[currentWinner]) 
                        currentWinner = persons[i];           
                }         
                winner.put(times[i], currentWinner);
            }
        }
        
        public int q(int t) { 
            if(winner.size() ==1) return persons[0];
            // 二分查找 t 位于哪个时间区间
            int l = 0, r = times.length - 1, index = -1;
            while(l < r){ 
                int mid = (r + l)/2;
                if(times[mid] == t) { index = mid;break;}
                else if(times[mid] > t) r = mid - 1;
                else l = mid + 1;
            }
            if(index == -1) index =  times[r] > t ? r - 1 : r;
            return winner.get(times[index]);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1h1X0pMMTk5Nw_size_16_color_FFFFFF_t_70]: /images/20220205/dd2c20ab16f94a7ca05f1a16a91a6776.png