网站定制套餐,网站开发 私活,网站前期准备工作,西安大雁塔音乐喷泉1. 题目
在未排序的数组中找到第 k 个最大的元素。请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k 2
输出: 5示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k 4
输出: 4说明:
你可以假设 k…1. 题目
在未排序的数组中找到第 k 个最大的元素。请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k 2
输出: 5示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k 4
输出: 4说明:
你可以假设 k 总是有效的且 1 ≤ k ≤ 数组的长度。来源力扣LeetCode 链接https://leetcode-cn.com/problems/kth-largest-element-in-an-array 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 快排解题
参考寻找数组内第K大的元素类似题目LeetCode 973. 最接近原点的 K 个点排序/优先队列/快排
class Solution { //C
public:int findKthLargest(vectorint nums, int k) {k nums.size()-k;//排序后的位置return findKthL(nums,k,0,nums.size()-1);}
private:void selectMid(vectorint nums, int left, int right){int mid left((right-left)1);if(nums[mid] nums[right])swap(nums[mid],nums[right]);if(nums[left] nums[right])swap(nums[left], nums[right]);if(nums[mid] nums[left])swap(nums[mid], nums[left]);}int findKthL(vectorint nums, int k, int left, int right){selectMid(nums,left,right);//三数取中int p nums[left];int i left, j right;while(i j){while(i j nums[j] p)j--;swap(nums[i], nums[j]);while(i j nums[i] p)i;swap(nums[i], nums[j]);}if(i k)return nums[i];else if(i k)return findKthL(nums,k,i1,right);elsereturn findKthL(nums,k,left,i-1);}
};class Solution { //C ,简化版
public:int findKthLargest(vectorint nums, int k) {return findk(nums,0,nums.size()-1, nums.size()-k);}int findk(vectorint nums, int l, int r, int k){int p nums[l];int i l, j r;while(i j){while(i j nums[j] p)j--;while(i j nums[i] p)i;swap(nums[i],nums[j]);}swap(nums[i], nums[l]);if(i k)return nums[i];if(i k)return findk(nums, i1, r, k);elsereturn findk(nums, l, i-1, k);}
};56 ms 9.9 MB
python3 解答
class Solution:# py3def findKthLargest(self, nums: List[int], k: int) - int:def findk(l, r, k):p nums[l];i lj rwhile i j:while i j and nums[j] p:j - 1while i j and nums[i] p:i 1t nums[i]nums[i] nums[j]nums[j] tt nums[i]nums[i] nums[l]nums[l] tif i k:return nums[i]elif i k:return findk(i1, r, k)else:return findk(l, i-1, k)return findk(0,len(nums)-1, len(nums)-k)1032 ms 19.7 MB
