2021-12-11 911. 在线选举

java版本

class TopVotedCandidate {
    List<Integer> tops;
    Map<Integer, Integer> voteCounts;
    int[] times;
    public TopVotedCandidate(int[] persons, int[] times) {
        tops = new ArrayList<Integer>();
        voteCounts = new HashMap<Integer, Integer>();
        voteCounts.put(-1, -1);
        int top = -1;
        for (int i = 0; i < persons.length; ++i) {
            int p = persons[i];
            voteCounts.put(p, voteCounts.getOrDefault(p, 0) + 1);
            if (voteCounts.get(p) >= voteCounts.get(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.get(l);
    }
}

// class TopVotedCandidate {

// // 哈希表
//  HashMap<Integer,Integer> hashmap=new HashMap<>();
//   int[] times_arr,res_arr;
// //   统计在某时刻,各个选举人的得票情况
// // 
//     public TopVotedCandidate(int[] persons, int[] times) {
//    times_arr=new int[times.length];
//      res_arr=times;
//        HashMap<Integer,Integer> getVoted=new HashMap<>();
       
//         int tmp=0,count=0;
//         for(int i=0;i<times.length;i++){
//             count=0;
//             times_arr[i]=times[i];
             
//             hashmap.put(times[i],persons[i]);
           
//             tmp=getVoted.getOrDefault(persons[i],0);
//             tmp++;
//             getVoted.put(persons[i],tmp);
//             // System.out.println();
//             int max=0,max_=0;
//             for(int j:getVoted.keySet()){
//                 // System.out.print(getVoted.get(j));
//                 if(max<getVoted.get(j)){
//                     max=getVoted.get(j);
//                     max_=j;
//                 }
//             }
//             res_arr[i]=max>tmp ? max_ : persons[i];
//             if(getVoted.get(persons[i])==max){
//                 res_arr[i]=persons[i];
//             }
//              for(int j:getVoted.keySet()){

//              }
            
           
//             // 两个相同的
            
//             // System.out.println(res_arr[i]);
            
//         }
//     }
    
//     public int q(int t) {
//         int res=0,key=0,res_key=0;

//      for(int i=0;i<times_arr.length;i++){
//         //  System.out.println(times_arr[i]);
//     //   System.out.println(hashmap.get(times_arr[i]));
//          key=t<times_arr[i] ? key : i;
        
//      }
//     //  System.out.print(res_key);

//        res=res_arr[key];
//        return res;
         

//     }
// }

// /**
//  * Your TopVotedCandidate object will be instantiated and called as such:
//  * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
//  * int param_1 = obj.q(t);
//  */