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.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
class Solution {
public void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
public int findKthLargest(int[] A, int k) {
k = A.length - k; // convert to index of k largest
int left = 0, right = A.length - 1;
while (left <= right) {
// Choosing left index as pivot element
int i = left;
for (int j = left + 1; j <= right; j++)
if (A[j] < A[left]) {
i++;
swap(A, j, i);
}
// 'i' will be the head of list of element < pivot
swap(A, left, i);
if (k < i)
right = i - 1;
else if (k > i)
left = i + 1;
else
return A[i];
}
return -1; // k is invalid
}
}