LeetCode 215. 数组中的第K个最大元素（快速排序）

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

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

说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

class Solution {	//C++
public:
    int findKthLargest(vector<int>& nums, int k) {
        k = nums.size()-k;//排序后的位置
        return findKthL(nums,k,0,nums.size()-1);
    }
private:
    void selectMid(vector<int>& nums, int left, int right)
    {
        int mid = left+((right-left)>>1);
        if(nums[mid] > nums[right])
            swap(nums[mid],nums[right]);
        if(nums[left] > nums[right])
            swap(nums[left], nums[right]);
        if(nums[mid] > nums[left])
            swap(nums[mid], nums[left]);
    }

    int findKthL(vector<int>& nums, int &k, int left, int right)
    {
        selectMid(nums,left,right);//三数取中
        int p = nums[left];
        int i = left, j = right;
        while(i < j)
        {
            while(i < j && nums[j] > p)
                j--;
            swap(nums[i], nums[j]);
            while(i < j && nums[i] <= p)
                i++;
            swap(nums[i], nums[j]);
        }
        if(i == k)
            return nums[i];
        else if(i < k)
            return findKthL(nums,k,i+1,right);
        else
            return findKthL(nums,k,left,i-1);
    }
};

class Solution {	//C++ ,简化版
public:
    int findKthLargest(vector<int>& nums, int k) {
        return findk(nums,0,nums.size()-1, nums.size()-k);
    }
    int findk(vector<int>& nums, int l, int r, int k)
    {
        int p = nums[l];
        int i = l, j = r;
        while(i < j)
        {
            while(i < j && nums[j] > p)
                j--;
            while(i < j && nums[i] <= p)
                i++;
            swap(nums[i],nums[j]);
        }
        swap(nums[i], nums[l]);
        if(i == k)
            return nums[i];
        if(i < k)
            return findk(nums, i+1, r, k);
        else
            return findk(nums, l, i-1, k);
    }
};

class Solution:# py3
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def findk(l, r, k):
            p = nums[l];
            i = l
            j = r
            while i < j:
                while i < j and nums[j] > p:
                    j -= 1
                while i < j and nums[i] <= p:
                    i += 1
                t = nums[i]
                nums[i] = nums[j]
                nums[j] = t
            t = nums[i]
            nums[i] = nums[l]
            nums[l] = t
            if i == k:
                return nums[i]
            elif i < k:
                return findk(i+1, r, k)
            else:
                return findk(l, i-1, k)
        return findk(0,len(nums)-1, len(nums)-k)