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 (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;
}
|
近期评论