陣列中的第K個最大元素
給定整數陣列 nums 和整數 k，請回傳陣列中第 k 個最大的元素，
思路
找到陣列中第k大的元素，可以直接排序，再找，但效率太低，不考慮
想到快速排序的每一趟排序，排完后基準值所在的位置右邊若有n個元素，基準值就是第n+1大，如果n+ 1 == k，那基準值就是我們要找的元素，如果n+ 1 > k，那我們要查找的值一定在基準值的右側，反之則是左側，因此我們可以利用快排來縮小范圍以便查找
代碼
class Solution {
public:
int partition(vector<int>& nums,int start,int end){
int pivot = nums[end];
int i= start;
for(int j = start;j < end;j++){ //順序快排
if(nums[j] <= pivot){
swap(nums[i++],nums[j]);
}
}
swap(nums[end],nums[i]);
return i;
}
int quickSelect(vector<int>& nums,int start,int end,int k){
int i = rand()% (end-start+1)+start; //生成隨機種子，優化快排
swap(nums[i],nums[end]);
int q = partition(nums, start, end);
if (q == k) {
return nums[q];
} else {
return q < k ? quickSelect(nums, q + 1, end, k) : quickSelect(nums, start, q - 1, k); //縮小范圍的重點
}
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(NULL));
return quickSelect(nums,0,nums.size()-1,nums.size()-k);//注意這里傳入的是nums.size()-k,這樣quickSelect里面就可以直接與之比較，不用轉化了
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/289119.html
標籤：其他
下一篇：leetcode-215