題目
https://leetcode.com/problems/online-election/
題解
我的解法是，用預計算（加強堆，O(nlogn)） + 二分查找（用的自帶TreeMap，查找復雜度O(logn)）。
實際上，最優解可以達到預計算 O(n)，只需要比較當前新元素的 count 與當前最大元素的 count，并更新最大元素即可。
下面來說一下為什么用加強堆。
系統自帶的堆，它不能動態修改元素。
就是說，已經入堆的元素，如果參與排序的指標方法變化，它不能自動調整。所以有了加強堆。
對于已經入堆的元素，它的字段發生改變的時候，能夠以O(logN)的復雜度調整整個堆。
class TopVotedCandidate {TreeSet<Info> treeSet
;public TopVotedCandidate(int[] persons
, int[] times
) {HeapGreater<Person> heap
= new HeapGreater<>((o1
, o2
) -> {if (o1
.count
!= o2
.count
) {return o2
.count
- o1
.count
;} else {return o2
.updatedTime
- o1
.updatedTime
;}});HashMap<Integer, Person> map
= new HashMap<>(); treeSet
= new TreeSet<>((o1
, o2
) -> o1
.time
- o2
.time
);for (int i
= 0; i
< persons
.length
; i
++) {if (!map
.containsKey(persons
[i
])) {Person p
= new Person(1, persons
[i
], times
[i
]);map
.put(persons
[i
], p
);heap
.push(p
);} else {Person p
= map
.get(persons
[i
]);p
.count
++;p
.updatedTime
= times
[i
];heap
.resign(p
);}treeSet
.add(new Info(heap
.peek().index
, times
[i
]));}}public int q(int t
) {return treeSet
.floor(new Info(-1, t
)).index
;}
}class Info {int index
;int time
;public Info(int index
, int time
) {this.index
= index
;this.time
= time
;}
}class Person {int count
;int index
;int updatedTime
;public Person(int count
, int index
, int updatedTime
) {this.count
= count
;this.index
= index
;this.updatedTime
= updatedTime
;}
}
class HeapGreater<T> {private ArrayList<T> heap
;private HashMap<T, Integer> indexMap
;private int heapSize
;private Comparator<? super T> comp
;public HeapGreater(Comparator<T> c
) {heap
= new ArrayList<>();indexMap
= new HashMap<>();heapSize
= 0;comp
= c
;}public T peek() {return heap
.get(0);}public void push(T obj
) {heap
.add(obj
);indexMap
.put(obj
, heapSize
);heapInsert(heapSize
++);}public void resign(T obj
) {heapInsert(indexMap
.get(obj
));heapify(indexMap
.get(obj
));}private void heapInsert(int index
) {while (comp
.compare(heap
.get(index
), heap
.get((index
- 1) / 2)) < 0) {swap(index
, (index
- 1) / 2);index
= (index
- 1) / 2;}}private void heapify(int index
) {int left
= index
* 2 + 1;while (left
< heapSize
) {int best
= left
+ 1 < heapSize
&& comp
.compare(heap
.get(left
+ 1), heap
.get(left
)) < 0 ? (left
+ 1) : left
;best
= comp
.compare(heap
.get(best
), heap
.get(index
)) < 0 ? best
: index
;if (best
== index
) {break;}swap(best
, index
);index
= best
;left
= index
* 2 + 1;}}private void swap(int i
, int j
) {T o1
= heap
.get(i
);T o2
= heap
.get(j
);heap
.set(i
, o2
);heap
.set(j
, o1
);indexMap
.put(o2
, i
);indexMap
.put(o1
, j
);}
}
總結
以上是生活随笔為你收集整理的leetcode 911. Online Election | 911. 在线选举（加强堆 + 二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
