中级农民
- 积分
- 155
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2014-4-17
- 最后登录
- 1970-1-1
|
写了下第二面的代码,quick selection的最大不好是输出是没有顺序的,如果要有序还得再排,minHeap就没有这个问题。
- public class Winner {
-
- static class LogEntry {
- String candidate;
- int time;
- public LogEntry(String candidate, int time) {
- this.candidate = candidate;
- this.time = time;
- }
- }
- static class People {
- String candidate;
- int votes;
- public People(String candidate, int votes) {
- this.candidate = candidate;
- this.votes = votes;
- }
- }
-
- public static String findWinner(int time, List<LogEntry> logs) {
- HashMap<String, Integer> map = new HashMap<String, Integer>();
- for (LogEntry entry : logs) {
- if (entry.time <= time) {
- if (map.containsKey(entry.candidate)) {
- map.put(entry.candidate, map.get(entry.candidate) + 1);
- } else {
- map.put(entry.candidate, 1);
- }
- }
- }
- String res = "";
- int max = 0;
- for (String candidate : map.keySet()) {
- if (map.get(candidate) > max) {
- res = candidate;
- max = map.get(candidate);
- }
- }
-
- return res;
- }
-
- public static List<String> findTopKWinner(int time, List<LogEntry> logs, int k) {
- HashMap<String, Integer> map = new HashMap<String, Integer>();
- for (LogEntry entry : logs) {
- if (entry.time <= time) {
- if (map.containsKey(entry.candidate)) {
- map.put(entry.candidate, map.get(entry.candidate) + 1);
- } else {
- map.put(entry.candidate, 1);
- }
- }
- }
- People[] candidates = new People[map.size()];
- int index = 0;
- for (String candidate : map.keySet()) {
- candidates[index++] = new People(candidate, map.get(candidate));
- }
- return topKCandidateQuickSelect(candidates, k);
- }
-
- private static List<String> topKCandidateQuickSelect(People[] candidates, int k) {
- List<String> res = new ArrayList<String>();
- if (k == candidates.length) {
- for (int i = 0; i < candidates.length; i++) {
- res.add(candidates[i].candidate);
- }
- return res;
- }
- int start = helper(candidates, 0, candidates.length - 1, k);
-
- for (int i = start; i < candidates.length; i++) {
- res.add(candidates[i].candidate);
- }
- return res;
- }
- private static int helper(People[] candidates, int start, int end, int k) {
- if (start > end) {
- return start;
- }
- int pos = quickSelect(candidates, start, end);
- if (pos == candidates.length - k) {
- return pos;
- } else if (pos < candidates.length - k) {
- return helper(candidates, pos + 1, end, k);
- } else {
- return helper(candidates, start, pos - 1, k);
- }
- }
- private static int quickSelect(People[] candidates, int start, int end) {
- int i = start;
- int j = start + 1;
- while (j <= end) {
- if (candidates[j].votes < candidates[start].votes) {
- i++;
- swap(candidates, i, j);
- j++;
- } else {
- j++;
- }
- }
- swap(candidates ,i, start);
- return i;
- }
- private static void swap(People[] candidates, int i, int j) {
- People tmp = candidates[i];
- candidates[i] = candidates[j];
- candidates[j] = tmp;
- }
- public static void main(String[] args) {
- LogEntry le1 = new LogEntry("c1", 1);
- LogEntry le2 = new LogEntry("c2", 2);
- LogEntry le3 = new LogEntry("c1", 2);
- LogEntry le4 = new LogEntry("c2", 3);
- LogEntry le5 = new LogEntry("c2", 4);
- List<LogEntry> logs = new ArrayList<LogEntry>();
- logs.add(le1);
- logs.add(le2);
- logs.add(le3);
- logs.add(le4);
- logs.add(le5);
- logs.add(new LogEntry("c3", 2));
- logs.add(new LogEntry("c3", 2));
- logs.add(new LogEntry("c3", 2));
- // System.out.println(findWinner(2, logs));
- // System.out.println(findWinner(4, logs));
- List<String> res = findTopKWinner(4, logs, 2);
- for (String str : res) {
- System.out.println(str);
- }
- }
- }
复制代码 |
|