Comment on page
215.Kth-Largest-Element-in-an-Array
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 int findKthLargest(int[] nums, int k) {
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> n1 - n2);
for (int n: nums) {
heap.add(n);
if (heap.size() > k) {
heap.poll();
}
}
return heap.poll();
}
}
class Solution {
int[] nums;
public int findKthLargest(int[] nums, int k) {
this.nums = nums;
int size = nums.length;
return quickselect(0, size - 1, size - k);
}
private int quickselect(int left, int right, int k) {
if (left == right) return nums[left];
int index = left + (right - left) / 2;
index = partition(left, right, index);
if (k == index) {
return nums[k];
} else if (k < index) {
return quickselect(left, index - 1, k);
} else {
return quickselect(index + 1, right, k);
}
}
private int partition(int left, int right, int index) {
int pivot = nums[index];
// 1. move pivot to end
swap(index, right);
// 2. move all smaller elements to the left
int start = left;
for (int i = left; i <= right; i++) {
if (nums[i] < pivot) {
swap(start, i);
start++;
}
}
// 3. move pivot to its final place
swap(start, right);
return start;
}
private void swap(int a, int b) {
int tmp = nums[a];
nums[a] = nums[b];
nums[b] = tmp;
}
}
Last modified 3yr ago