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.
Solution:
1. Sorting:
class Solution {public int findKthLargest(int[] nums, int k)
{
Arrays.sort(nums);
return nums[nums.length -k];
}
2. Heap:
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>(k);
for(int i: nums){
queue.offer(i);
if(queue.size()>k){
queue.poll();
}
}
return queue.peek();
}
3. Partitioning:
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
int left = 0;
int right = n - 1;
Random rand = new Random(0);
while (left <= right) {
int choosenIndex = rand.nextInt(right - left + 1) + left;
int finalIndex = partition(nums, left, right, choosenIndex);
if (finalIndex == n - k) {
return nums[finalIndex];
} else if (finalIndex > n - k) {
right = finalIndex - 1;
} else {
left = finalIndex + 1;
}
}
return -1;
}
private int partition(int[] arr, int left, int right, int pivotIndex) {
int pivotValue = arr[pivotIndex];
int lesserIndex = left;
swap(arr, pivotIndex, right);
for (int i = left; i < right; i++) {
if (arr[i] < pivotValue) {
swap(arr, i, lesserIndex);
lesserIndex++;
}
}
swap(arr, right, lesserIndex);
return lesserIndex;
}
private void swap(int[] arr, int first, int second) {
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
}
Comments