- min Heap with size of K, do not think always keep the min element, but polll when the size of minheap is K
- PriorityQueue minHeap = new PriorityQueue((n1, n2)->(n1-n2));
class Solution {
public int findKthLargest(int[] nums, int k) {
//min heap: remove min element
//time: O(nlgk) since need lgk to add the element
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>((n1, n2)-> n1-n2);
//keep k largest elements in the heap
for(int ele : nums){
minHeap.add(ele);
if(minHeap.size()>k){
minHeap.poll();
}
}
return minHeap.poll();
}
}
- quick select and time is O(n) worst case is O(n^2), O(T) = 2O(T/2) + n
- exactly using quick sort template
- kth largest (1=<k<=size) -> size-k th smallest (0,1,2,...size-1)
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums.length==0) return -1;
return quickSelect(nums,nums.length-k, 0, nums.length-1 );
}
int quickSelect(int[] nums, int k, int start, int end){
int pos = partition(nums, start, end);
if(pos<k){
return quickSelect(nums, k, pos+1, end);
}else if(pos==k){
return nums[pos];
}else{
return quickSelect(nums, k, start, pos-1);
}
}
//此函数把array 分割成两部分，左面小于A[pivot]，右面大于。同时此函数return the position/index of the pivot element
//3 1 2 45 -> 1 2 3 45and return index of the pivot
int partition(int A[], int start, int end) {
int i = start + 1; //[i] pointing to the first element larger than pivot
int piv = A[start];
//use 2 1 9 10 0 as example
for (int j = start + 1; j <= end; j++) {
if (A[j] < piv) { //when A[j] smaller than it, need to swap i and j
swap(A, i, j);
i++;
}
}
swap(A, start, i - 1); //swap piv and last element smaller than pivot
return i - 1; //position of pivot // |element less than piv| piv |ele greater than piv|
}
void swap(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}