在数组中找到第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;
}
};
