https://leetcode-cn.com/problems/kth-largest-element-in-an-array/submissions/

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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        quicksort(nums, 0, len - 1);
        return nums[len - k];
    }
    void quicksort(vector<int>& nums, int i, int j) {
        if(i == j) {
            return;
        }
        int top = i;
        int ed = j;
        int tmp = nums[i];
        while(i < j) {
            while(i < j && nums[j] >= tmp) {
                j--;
            }
            nums[i] = nums[j];
            while(i < j && nums[i] <= tmp) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = tmp;
        if(top < i - 1) {
            quicksort(nums, top, i - 1);
        }
        if(ed > j + 1) {
            quicksort(nums, j + 1, ed);
        }
    }
};
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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        qk(nums, 0, len - 1);
        for(int i = 0 ; i < len ; i++) {
            cout << nums[i] << '\n';
        }
        return nums[len - k];
    }
    int quicksort(vector<int>& nums, int i, int j) {
        int tmp = nums[i];
        while(i < j) {
            while(i < j && nums[j] >= tmp) {
                j--;
            }
            nums[i] = nums[j];
            while(i < j && nums[i] <= tmp) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = tmp;
        return i;
    }
    void qk(vector<int>& nums, int i, int j) {
        if(i < j) {
            int idx = quicksort(nums, i, j);
            qk(nums, i, idx - 1);
            qk(nums, idx + 1, j);
        }
    }
};