1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int quick_sort(vector<int>& nums, int l, int r, int k) {
        if (l == r) return nums[l];

        int x = nums[l + r >> 1];
        int i = l - 1, j = r + 1;
        while (i < j) {
            while (nums[++i] > x);
            while (nums[--j] < x);
            if (i < j) swap(nums[i], nums[j]);
        }

        if (k <= j) return quick_sort(nums, l, j, k);
        return quick_sort(nums, j + 1, r, k);
    }

    int findKthLargest(vector<int>& nums, int k) {
        return quick_sort(nums, 0, nums.size() - 1, k - 1);
    }
};

 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

class Solution {
public:
    void down(vector<int>& h, int u, int size) {
        int t = u;
        if (u * 2 <= size && h[u * 2] > h[t]) t = 2 * u;
        if (u * 2 + 1 <= size && h[u * 2 + 1] > h[t]) t = 2 * u + 1;
        if (u != t) {
            swap(h[u], h[t]);
            down(h, t, size);
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        vector<int> h;
        h.push_back(0);

        for (int i = 0; i < nums.size(); i ++) {
            h.push_back(nums[i]);
        }

        for (int i = nums.size() / 2; i > 0; i --) down(h, i, nums.size());

        int size = nums.size();
        for (int i = 0; i < k - 1; i ++) {
            h[1] = h[size];
            down(h, 1, -- size);
        }

        return h[1];
    }
};