0%

Kth Largest Element in an Array

Question

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

Solution

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
44
45
46
47
48
49
50
//用partition来解 O(n)
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return -1;
}
if (k <= 0 || k > nums.length) {
return -1;
}

int res = partition(nums, 0, nums.length-1, k-1);
for (int n : nums) {
System.out.print(n+" ");
}
return res;
}

// 这里k代表index
public int partition(int[] nums, int start, int end, int k) {
if (start >= end) {
return nums[k];
}

int left = start, right = end;
int pivot = nums[start+(end-start)/2];

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

while (left <= right && nums[right] < pivot) {
right--;
}
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}

if (k <= right) {
return partition(nums, start, right, k);
}
if (k >= left) {
return partition(nums, left, end, k);
}
return nums[k];
}