字节跳动-面试 二分法解决 第K大的数字

 

class Solution {
public:
    int partition(int low, int high , vector<int>&v)
    {
        int key=v[low],l=low, h=high;
        while(l<h)
        {
            while(l<h && v[h]>key) h--;
            while(l<h && v[l]<=key) l++;
            swap(v[l],v[h]); 
        }
        swap(v[low],v[l]);
        return l;
    } 
    int findKthLargest(vector<int>& nums, int k) 
    {
        int index=partition(0,nums.size()-1,nums);
        while(index!=nums.size()-k)
        {
            if(index>nums.size()-k)
            index=partition(0,index-1,nums);
            else 
            index=partition(index+1,nums.size()-1,nums);
        }
        return nums[index];
    }
};