LeetCode: 数组中的第K个最大元素
问题描述
在未排序的数组中找到第k个最大的元素。请注意,你需要找的是数组排序后的第k个最大的元素,而不是第k个不同的元素。
解题思路
解决这个问题有多种方法,下面是几种常见的解题策略:
- 排序后选择: 将数组排序,然后选择第
len(array) - k
位置上的元素。 - 优先队列(最小堆): 使用一个大小为k的最小堆,遍历数组维护堆的大小为k,堆顶即为第k个最大元素。
- 快速选择(QuickSelect): 快速选择算法是快速排序的变体,用于找到未排序数组中第k个最大的元素。
代码示例
排序后选择
class Solution:
def findKthLargest(self, nums, k):
nums.sort()
return nums[-k]
这种方法的时间复杂度为O(NlogN),空间复杂度为O(1)(如果使用的是原地排序算法)。
优先队列(最小堆)
import heapq
class Solution:
def findKthLargest(self, nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
这种方法的时间复杂度为O(NlogK),空间复杂度为O(K)。
快速选择(QuickSelect)
class Solution:
def findKthLargest(self, nums, k):
k = len(nums) - k
def quickselect(l, r):
pivot, p = nums[r], l
for i in range(l, r):
if nums[i] <= pivot:
nums[p], nums[i] = nums[i], nums[p]
p += 1
nums[p], nums[r] = nums[r], nums[p]
if p > k: return quickselect(l, p - 1)
if p < k: return quickselect(p + 1, r)
return nums[p]
return quickselect(0, len(nums) - 1)
int partition(vector<int>& nums,int left,int right)
{
int key = nums[left];
while(left < right)
{
while(left < right and nums[right] >= key )
{
right--;
}
nums[left] = nums[right]
while(left < right and nums[left] <= key )
{
left++;
}
nums[right] = nums[left]
}
nums[left] = key;
return left;
}
int findk(vector<int>& nums)
{
random_shuffle(nums.begin(),nums.end());
int n = nums.size();
int left = 0,rihgt = n-1;
while(True)
{
int p = partition(nums,left,right);
if(p == n-k)
{return nums[p];}
else if(p > n-k)
{
right = p-1;
}
else
{
left = p +1;
}
}
return -1;
}
快速选择的平均时间复杂度为O(N),最坏情况下的时间复杂度为O(N^2),空间复杂度为O(1)。