[LeetCode] Problem 215 - Kth Largest Element in an Array

Posted on | In ,

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

No.1

Input: [3,2,1,5,6,4] and k = 2

Output: 5

No.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.

Code

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
public int findKthLargest(int[] nums, int k) {
    return sort(nums, k, 0, nums.length - 1);
}

private int sort(int[] nums, int k, int left, int right) {
    int pivot = partition(nums, left, right);

    if (pivot == nums.length - k)
        return nums[pivot];
    else if (pivot < nums.length - k)
        return sort(nums, k, pivot + 1, right);
    else
        return sort(nums, k, left, pivot - 1);
}

private int partition(int[] nums, int left, int right) {
    int pivot = left;

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

        while (left <= right && nums[right] > nums[pivot])
            right--;

        if (left > right)
            break;

        swap(nums, left, right);
    }

    swap(nums, pivot, right);

    return right;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}