215. 数组中的第K个最大元素#

1
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
2

3
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
4

5

6

7
示例 1:
8

9
输入: [3,2,1,5,6,4] 和 k = 2
10
输出: 5
11
示例 2:
12

13
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
14
输出: 4
15

16

17
提示：
18

19
1 <= k <= nums.length <= 104
20
-104 <= nums[i] <= 10^4

1
class Solution{
2
public:
3
    void heap_sort(vector<int>&ans, int i, int n) {
4
        int l = i * 2 + 1, r = i * 2 + 2, max = i;
5

6
        if (l < n && ans[l] > ans[max]) max = l;
7
        if (r < n && ans[r] > ans[max]) max = r;
8

9
        if (max != i)
10
        {
11
            swap(ans[i], ans[max]);
12
            heap_sort(ans, max, n);
13
        }
14
    }
15

16
    void buildHeap(vector<int>& ans, int n) {
17
        for (int i = n / 2; i >= 0; --i) heap_sort(ans, i, n);
18
    }
19

20
    int findKthLargest(vector<int>& nums, int k) {
21
        int n = nums.size();
22
        buildHeap(nums, n);
23
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; i--)
24
        {
25
            swap(nums[0], nums[i]);
26
            --n;
27
            heap_sort(nums, 0, n);
28
        }
29
        return nums[0];
30
    }
31
};