class KthLargestElementQuickSelect {
static Random random = new Random();
public int findKthLargest3(int[] nums, int k) {
return select(nums, 0, len - 1, len - k);
private int select(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
// random select pivotIndex between left and right
int pivotIndex = left + random.nextInt(right - left);
// do partition, move smaller than pivot number into pivot left
int pos = partition(nums, left, right, pivotIndex);
return select(nums, left, pos - 1, k);
return select(nums, pos + 1, right, k);
private int partition(int[] nums, int left, int right, int pivotIndex) {
int pivot = nums[pivotIndex];
swap(nums, right, pivotIndex);
// move smaller num to pivot left
for (int i = left; i <= right; i++) {
// move pivot to original place
private void swap(int[] nums, int i, int j) {