Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.
For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30 and 23.
Solution1: minHeap
此处找的是k个最大elements，也可以先把array sort一下，然后直接取k个。复杂度和minHeap一样。
Min heap是把最小的从queue里踢出，所以最后留下的是最大的。
In a Min Heap this property will be “If A is a parent node of B then key(A) is less than key(B) with the same ordering applying across the heap.”
And in a max heap the key(A) will be greater than Key(B).
public class FindKMaximumInteger {
public static void main(String[] args) {
int[] arr = { 3, 46, 2, 56, 3, 38, 93, 45, 6, 787, 34, 76, 44, 6, 7, 86, 8, 44, 56 };
int k = 5;
int[] result = findKMaximum(arr, k);
for (int i : result) {
System.out.print(i + ",");
}
}
public static int[] findKMaximum(int[] n, int k) {
if(n == null || n.length == 0) {
return null;
}
PriorityQueue minHeap = new PriorityQueue();
for(int i = 0; i < n.length; i++) {
int cur = n[i];
if(minHeap.size() < k) {
minHeap.add(cur);
}else if(cur > minHeap.peek()){ // 如果find kth minimum integer， 此处换成cur < minHeap.peek()
minHeap.poll(); //poll()踢出的是根元素
minHeap.add(cur);
}
}
int[] res = new int[k];
int index = 0;
while(minHeap.size() != 0) {
res[index] = minHeap.poll();
index++;
}
return res;
}
}
Solution2:
quick select
此处找的是第k个最大element。quick select 还可以用于找中位数的题。
Like with quicksort, select a random element from the list, and place every item that is smaller to the first half of the array, and every element that is equal to or greater than the pivot, in the second half (the ‘half’ is not entirely correct, as it is possible that the result will not be exactly ‘half’).
如果是找第k个最大，则把大于等于pivot的放在左侧，小于pivot的放在右侧。
如果是找第k个最小，则相反。
时间复杂度是O(n).
//Quick select!
public static int findKth(int[] n, int k) {
if(n == null || n.length < k) {
return 0;
}
int l = 0, r = n.length - 1;
while(l < r) {
int pivot = (l + r) / 2;
int pivotValue = n[pivot];
int store = l;
n[pivot] = n[r];
n[r] = pivotValue;
for(int i = l; i < r; i++) {
//for each number, if its greater than the pivot, move it to the left, otherwise leave it on the right
if(n[i] > pivotValue) { //if we want to find kth SMALLEST, change to n[i] < pivotValue
int temp = n[store];
n[store] = n[i];
n[i] = temp;
store++;
}
}
n[r] = n[store];
n[store] = pivotValue; //move the pivot to its correct absolute location in the list
//pick the correct half of the list you need to parse through to find your K, and ignore the other half
if(store < k) {
l = store + 1;
}else {
r = store;
}
}
return n[k];
}
. For example, if n = 0, then fib() should return 0. If n = 1, then it should return 1. For n > 1, it should return 