点击：题目链接：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
思路
直接的思路，就是将数组排序好，然后取出第k个最大的数组。这里我们选择快排。时间复杂度最小。
代码
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
| class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
quicksort(nums, 0, nums.size()-1);
return nums[nums.size()-k];
}
void quicksort(vector<int>& v, int L, int R) {
if (L >= R) return;
int temp = v[L];
int L_pre = L;
int R_pre = R;
while (L < R) {
while (L<R && v[R] > temp) --R;
v[L] = v[R];
while (L<R && v[L] <= temp) ++L;
v[R] = v[L];
}
v[L] = temp;
quicksort(v, L_pre, L - 1);
quicksort(v, L + 1, R_pre);
}
};
|
复杂度
时间：O（nlogn）， 空间，O（n）
思路
另一个思路，就是用partition算法。我们可以选择一个数（可随机），然后和剩下的数一一比较，若左边的数大于当前的数，就交换他们，最终保证左边的数都比当前的数小。这样我们可以快速找到我们需要的值，而无须排序好整个数组。
代码
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
| class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
if(nums.size() == 1) return nums[0];
int target = nums.size()-k;
int L = 0;
int R = nums.size()-1;
while (1) {
int index = partition(nums, L, R);
if (index < target) {
L = index + 1;
}
else if (index > target) {
R = index - 1;
}
else {
break;
}
}
return nums[target];
}
int partition(vector<int>& v, int L, int R) {
int pivote = v[L];
int j = L;
for (int i = j+1; i <= R; ++i) {
if (v[i] < pivote) {
j++;
swap(v[i], v[j]);
}
}
swap(v[j], v[L]);
return j;
}
};
|
复杂度
时间：O(N), 空间O(1)