leetcode 215. Kth Largest Element in an Array

原题传送门 ->Kth Largest Element in an Array

Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:

You may assume k is always valid, 1 ≤ k ≤ array’s length.

标准的快排思想题。
只是我的快排还要写多少遍能熟练呢😭

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return findKth(nums,0,nums.size()-1,nums.size()-k);
    }
    int findKth(vector<int>& nums, int left, int right,int k){
        int l = left, r = right;//错点
        while(l < r){
            while((nums[r] >= nums[left])&&(l < r)) --r;
            while((nums[l] <= nums[left])&&(l < r)) ++l;
            if(l < r)
            swap(nums[l],nums[r]);
        }
        swap(nums[left],nums[l]);
        if(l == k) return nums[l];
        if(l < k) return findKth(nums,l+1,right,k);
        else return findKth(nums,left,l-1,k);
    }
};

一开始我把l初始化为left+1就一直错。
原因是当left=right时会出问题。