Theory
Implementation in Java
class Solution {
void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
int partition(int[] nums, int start, int end, int pivot) {
int val = nums[pivot];
swap(nums, pivot, end - 1);
int x = start;
for (int i = start; i + 1 < end; i++) {
if (nums[i] < val) {
swap(nums, x, i);
x++;
}
}
swap(nums, x, end - 1);
return x;
}
public int findKth(int[] nums, int k) {
int low = 0, high = nums.length;
while (low < high) {
if (low + 1 == high) {
return nums[low];
}
int x = low + (high - low) / 2;
int pivot = partition(nums, low, high, x);
if (pivot + 1 == k) {
return nums[pivot];
}
if (pivot + 1 < k) {
low = pivot + 1;
} else {
high = pivot;
}
}
return -1;
}
public int findKthLargest(int[] nums, int k) { return findKth(nums, nums.length - k + 1); }
}
Practice