洪山网站建设,域名购买之后怎么做网站,昆明网站设计,中国建筑装饰网平台问题描述
在未排序的数组中找到第k个最大的元素。请注意#xff0c;你需要找的是数组排序后的第k个最大的元素#xff0c;而不是第k个不同的元素。
解题思路
解决这个问题有多种方法#xff0c;下面是几种常见的解题策略#xff1a;
排序后选择: 将数组排序#xff0c…问题描述
在未排序的数组中找到第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 heapqclass 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) - kdef quickselect(l, r):pivot, p nums[r], lfor i in range(l, r):if nums[i] pivot:nums[p], nums[i] nums[i], nums[p]p 1nums[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(vectorint 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(vectorint 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)。
