两种做法
一是用 minheap，在 Java 里就是 PriorityQueue，O(logn) time, O(k) space
``` java
public class LargestKIntegers {
public class TopList<T extends Comparable<T>> {
private final int _capacity;
private final PriorityQueue<T> _minHeap;
public TopList(int capacity) {
_capacity = capacity + 1;
_minHeap = new PriorityQueue<T>(capacity);
}
public void add(T nextValue) {
_minHeap.offer(nextValue);
if (_minHeap.size() >= _capacity) _minHeap.poll();
}
public Collection<T> getTop() {
return new ArrayList<T>(_minHeap);
}
}
@
Test public void keepLargest5() {
TopList<Integer> list = new TopList<Integer>(5);
for (int i = 0; i < 10; i++) {
list.add(i);
}
for (int i = -1; i >= -100; i--) {
list.add(i);
}
Collection<Integer> rst = list.getTop();
Assert.assertEquals(5, rst.size());
for (int i = 5; i < 10; i++) {
Assert.assertTrue(rst.contains(i));
}
}
}
```
第二种做法是类似 quick sort 里面的 partition
``` java
// Use partition in quicksort
// Expected: N + N/2 + N/4 + ... = N
// Worst-case: N^2
// Side effect: largest K integers will be in [K... N-1] subarray
public class KthLargestElement {
public int kthLargestElement(int k, ArrayList<Integer> numbers) {
int rank = partition(numbers, 0, numbers.size() - 1);
while (rank != k) {
if (rank < k) {
rank = partition(numbers, rank-1 + 1, numbers.size() - 1);
} else {
rank = partition(numbers, 0, rank-1 - 1);
}
}
return numbers.get(rank-1);
}
int partition(List<Integer> a, int s, int e) {
int j = s;
int midVal = a.get(e);
for (int i = s; i <= e; i++) {
if (a.get(i) >= midVal) {
int tmp = a.get(j);
a.set(j, a.get(i));
a.set(i, tmp);
j++;
}
}
return j;
}
}
```