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
| class Solution {
private:
int res;
public:
int findKthLargest(vector<int> &nums, int k) {
quickSort(nums, 0, nums.size() - 1, k);
return res;
}
void quickSort(vector<int> &nums, int left, int right, int k) {
if (left > right) {
return;
}
int l = left + 1, r = right;
int pivot = nums[left];
while (l <= r) {
while (l <= r && nums[l] <= pivot) {
++l;
}
while (l <= r && nums[r] > pivot) {
--r;
}
if (l < r) {
swap(nums[l++], nums[r--]);
}
}
swap(nums[r], nums[left]);
if (r == nums.size() - k) {
res = nums[r];
return;
} else if (r > nums.size() - k) {
quickSort(nums, left, r - 1, k);
} else {
quickSort(nums, r + 1, right, k);
}
}
};
|
