This is one of the solution for Kth Largest Element in an Array.

We have already understood the problem here - Kth Smallest Element Using Randomized Selection.

Pivot at the end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

public int findKthLargest(int[] nums, int k) {
	return quickSelect(nums, nums.length - k + 1, 0, nums.length - 1);
}

int quickSelect(int[] nums, int k, int start, int end) {
	int pivot = nums[end];

	int left = start;
	int right = end;

	while (true) {

		while (nums[left] < pivot && left < right) {
			left++;
		}

		while (nums[right] >= pivot && right > left) {
			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 quickSelect(nums, k, start, left - 1);
	} else {
		return quickSelect(nums, k, left + 1, end);
	}
}

void swap(int[] A, int i, int j) {
	int tmp = A[i];
	A[i] = A[j];
	A[j] = tmp;
}

Using randomized pivot

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    private final Random rnd = new Random();
    public int findKthLargest(int[] nums, int k) {
        int index = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int pivotIdx = partition(nums, lo, hi);
            if (pivotIdx == index) {
                break;
            } else if (pivotIdx < index) {
                lo = pivotIdx + 1;
            } else {
                hi = pivotIdx - 1;
            }
        }
        return nums[index];
    }
    
    private int partition(int[] nums, int lo, int hi) {
        swap(nums, hi, lo + rnd.nextInt(hi - lo));
        int pivot = nums[hi];
        int j = lo;
        for (int i = lo; i < hi; i++) {
            if (nums[i] < pivot) {
                swap(nums, i, j++);
            }
        }
        swap(nums, hi, j);
        return j;
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}