Kth Largest Element in an Array(Medium)
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example, Given [3,2,1,5,6,4] and k = 2, return 5.
Note: You may assume k is always valid, 1 ≤ k ≤ array's length.
解法1:最小堆
复杂度:时间 O(NlogK) 空间 O(K)
public int findKthLargest(int[] nums, int k) {
final PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int val : nums) {
minHeap.offer(val);
if(minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
解法1:QuickSelect
复杂度:时间 Avg O(N) Worst O(N^2) 空间 O(1)
public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
final int j = partition(nums, lo, hi);
if(j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
break;
}
}
return nums[k];
}
private int partition(int[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
while(true) {
while(i < hi && less(a[++i], a[lo]));
while(j > lo && less(a[lo], a[--j]));
if(i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
private void exch(int[] a, int i, int j) {
final int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
private boolean less(int v, int w) {
return v < w;
}