6/29刷题

1.数组中的第k个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 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 ≤ 数组的长度。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
思路：基于快排的查找算法

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len=nums.size();
        int start=0,end=len-1;
        int index=Partition(nums,len,start,end);
        int cur=len-k;
        while(index!=cur)
        {
            if(index>cur)
            {
                end=index-1;
                index=Partition(nums,len,start,end);
            }
            else
            {
                start=index+1;
                index=Partition(nums,len,start,end);
            }
        }
        return nums[index];
    }
    int Partition(vector<int> &numbers,int length,int start,int end)//快排核心函数
    {
        if(length<=0||start<0||end>=length)
            return false;
        int index=RandomInRange(start,end);
        Swap(&numbers[index],&numbers[end]);//随机生成一个点，与尾结点互换
        int small=start-1;
        for(index=start;index<end;index++)
        {
            if(numbers[index]<numbers[end])
            {
                ++small;
                if(small!=index)
                    Swap(&numbers[index],&numbers[small]);//说明small与index之间有大于end下标的数字
            }
        }
        ++small;
        Swap(&numbers[small],&numbers[end]);
        return small;
    }
    int RandomInRange(int start,int end)
   {
         srand (time(NULL));
         return rand() % (end-start+1) + start;//随机数函数
   }
    void Swap(int *a,int *b)
    {
        int temp=*a;
        *a=*b;
        *b=temp;
    }
};