partition(vector<
int>& nums,
intlow,
int high) { 5inttemp =
nums[low]; 6//对数列进行遍历,将比temp小的数搬到左边,比temp大的数搬到右边。 7while(low <
high) { 8while((low < high) && (nums[high] >
temp)) 9high--
; 10if(low <
high) 11nums[low++] =
nums[high]; 12while((low < high) && (nums[low] <
temp)) 13low ++
; 14if(low <
high) 15nums[high--] =
nums[low]; 16 } 17nums[low] =
temp; 18return low; 19 } 20voidquicksort(vector<
int>& nums,
intlow,
inthigh,
int k) { 21if(low <
high) { 22// 对所得的两段序列进行判断,第K大的数在哪个序列中,则对哪个序列进一步排序。23intmid =
partition(nums,low,high); 24if(mid > nums.size() -
k) 25quicksort(nums,low,mid-
1,k); 26if(mid < nums.size() -
k) 27quicksort(nums,mid+
1,high,k); 28 } 29 } 30intfindKthLargest(vector<
int>& nums,
int k) { 31quicksort(nums,
0, nums.size()-
1,k); 32returnnums[nums.size() -
k]; 33 } 34};
来源: http://www.bubuko.com/infodetail-1969504.html