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.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
Constraints
Approach
Links
GeeksforGeeks
ProgramCreek
YouTube
Examples
Input: [3, 2, 1, 5, 6, 4] and k = 2
Output: 5
Input: [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4
Output: 4
Solutions
/**
* Time complexity : O(NlogN)
* Space complexity : O(1)
*/
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}
/**
* Time complexity : O(N)
* Space complexity : O(N)
*/
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue(k);
for(int n: nums) {
queue.offer(n);
if(queue.size() > k) {
queue.poll();
}
}
return queue.peek();
}
}
/**
* Time complexity : O(N) in the average case, O(N^2)in the worst case.
* Space complexity : O(1)
*/
class Solution {
public int findKthLargest(int[] nums, int k) {
return qs(nums, nums.length-k+1, 0, nums.length-1);
}
private int qs(int[] nums, int k, int start, int end) {
int left = start,
right = end;
int pivot = nums[end];
while(true) {
while(left < right && nums[left] < pivot) {
left++;
}
while(right > left && nums[right] >= pivot) {
right--;
}
if(left == right) break;
swap(nums, left, right);
}
swap(nums, left, end);
if(k == left+1) {
return pivot;
} else if(k < left+1) {
return qs(nums, k, start, left-1);
} else {
return qs(nums, k, left+1, end);
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}