在未排序的数组中找到第 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution { //C++
public:
int findKthLargest(vector<int>& nums, int k) {
k = nums.size()-k;//排序后的位置
return findKthL(nums,k,0,nums.size()-1);
}
private:
void selectMid(vector<int>& 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(vector<int>& 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,i+1,right);
else
return findKthL(nums,k,left,i-1);
}
};
class Solution { //C++ ,简化版
public:
int findKthLargest(vector<int>& nums, int k) {
return findk(nums,0,nums.size()-1, nums.size()-k);
}
int findk(vector<int>& 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, i+1, r, k);
else
return findk(nums, l, i-1, k);
}
};
56 ms 9.9 MB
python3 解答
class Solution:# py3
def findKthLargest(self, nums: List[int], k: int) -> int:
def findk(l, r, k):
p = nums[l];
i = l
j = r
while i < j:
while i < j and nums[j] > p:
j -= 1
while i < j and nums[i] <= p:
i += 1
t = nums[i]
nums[i] = nums[j]
nums[j] = t
t = nums[i]
nums[i] = nums[l]
nums[l] = t
if i == k:
return nums[i]
elif i < k:
return findk(i+1, r, k)
else:
return findk(l, i-1, k)
return findk(0,len(nums)-1, len(nums)-k)
1032 ms 19.7 MB