第k大元素

在数组中找到第k大的元素

 注意事项

你可以交换数组中的元素的位置

您在真实的面试中是否遇到过这个题？ Yes
样例
给出数组 [9,3,2,4,8]，第三大的元素是 4

给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推

第一种方法 快排变种

class Solution {
public:
    /*
     * param k : description of k
     * param nums : description of array and index 0 ~ n-1
     * return: description of return
     */
    int kthLargestElement(int k, vector<int> nums) {
        // write your code here
        int result = 4;
        find(nums,0,nums.size()-1,k,result);
        return result;
    }
    
    void find(vector<int>&nums,int left,int right,int k,int& result) {
        
        
        if (left == right) {
            result = nums[left];
            return;
        }
        
        int pvoit = nums[right];

        int mid = partition(nums,pvoit,left,right);
        int temp = nums[mid];
        nums[right] = temp;
        nums[mid] = pvoit;
   //分治思想 分到最后都会有mid - left + 1 == k
        if (mid - left + 1 == k) {
            result = nums[mid]; 
        } else if (mid -1 - left + 1 >= k) {
             find(nums,left,mid-1,k,result);
        } else if (mid - left + 1 < k) {
            find(nums,mid+1,right,k - mid + left - 1,result);
        }
        
    }
    
    int partition(vector<int>&nums,int pvoit,int left,int right) {
        int i = left-1;
        int j = right;
        
        while( i < j ) {
          while(i < j && nums[++i] > pvoit);
          while(i < j && nums[--j] < pvoit);
          
          int temp = nums[i];
          nums[i] = nums[j];
          nums[j] = temp;
          
        }
        
        return j;

    }
    
};