Google-Find Winner

Google-Find Winner
有一个class代表投票，candidate是投给谁，time是投票时间。
class LogEntry {
String candidate;
int time;
}
[Problem]
问题是给一个List<LogEntry>和一个时间，求截止到这个时间为止得票最多的candidate。
[Follow up]
求截止到这个时间为止的top k
[Solution]
典型的k smallest number/quick select 问题
用Hash table存每个candidate的得票数，然后用quick select algorithm
[Time&Space]
O(n) average, O(n^2) worst case
O(n) space

class LogEntry {

  String candidate;

  int time;

   

  public LogEntry(String candidate, int time) {

    this.candidate = candidate;

    this.time = time;

  }

}

 

class Solution {

  public List<String> findKWinner(int time, List<LogEntry> logs, int k) {

    List<String> result = new ArrayList<>();

    if (logs == null || logs.isEmpty()) {

      return result;

    }

     

    Map<String, Integer> map = new HashMap<>();

    for (LogEntry log : logs) {

      if (log.time <= time) {

        map.put(log.candidate, map.getOrDefault(log.candidate, 0) + 1);

      }

    }

     

    List<Map.Entry<String, Integer>> list = new ArrayList<>();

    list.addAll(map.entrySet());

     

    int value = kthSmallest(list, 0, list.size() - 1, map.size() - k);

    for (String candidate : map.keySet()) {

      if (map.get(candidate) > value) {

        result.add(candidate);

      }

    }

     

    return result;

  }

    

  private int kthSmallest(List<Map.Entry<String, Integer>> list, int l, int r, int k) {

    int index = partition(list, l, r);

    int cnt = index - l + 1;

    if (cnt == k) {

      return list.get(index).getValue();

    }

    else if (cnt > k) {

      return kthSmallest(list, l, index - 1, k);

    }

    else {

      return kthSmallest(list, index + 1, r, cnt - k);

    }

     

  }

   

  private int partition(List<Map.Entry<String, Integer>> list, int l, int r) {

    int pivot = list.get(l).getValue();

    int left = l;

    int right = r + 1;

    while (true) {

      while (++left < r && list.get(left).getValue() < pivot);

      while (--right > l && list.get(right).getValue() > pivot);

       

      if (left < right) {

        swap(list, left, right);

      }

      else{

        break;

      }

    }

     

    swap(list, right, l);

    return right;

  }

   

  private void swap(List<Map.Entry<String, Integer>> list, int l, int r) {

    Map.Entry<String, Integer> tmp = list.get(l);

    list.set(l, list.get(r));

    list.set(r, tmp);

  }

}

Read full article from Google-Find Winner