电商设计师联盟网站/企业建站模板

215.数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 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

提示：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
https://leetcode-cn.com/problems/kth-largest-element-in-an-array

第一种解法：快排
快排的第一种实现：选择前、中、后三者的中位数作为主元，把主元放到right-1位置，此时待划分部分为[left+1, right-2]，因为left位置一定比主元小，right一定比主元大，right-1为主元位置。另外，对于等于主元的元素也执行交换操作，这样对于全部为一个值的数组而言，每次划分正好平均分成两部分，尽管执行了交换操作。如果不做处理，会导致每次只能划分一个区间，此时的时间复杂度为$O(n^2)$。

def getPivot(nums, left, right):center = (left + right) // 2if nums[left] > nums[center]:nums[left], nums[center] = nums[center], nums[left]if nums[left] > nums[right]:nums[left], nums[right] = nums[right], nums[left]if nums[center] > nums[right]:nums[center], nums[right] = nums[right], nums[center]nums[right-1], nums[center] = nums[center], nums[right-1]return nums[right-1]
def qsort(nums, left, right):if right - left < 1:return Nonepivot = getPivot(nums, left, right)i = leftj = right-1while i < j:i += 1j -= 1while nums[i] < pivot:i += 1while nums[j] > pivot:j -= 1if i < j:nums[i], nums[j] = nums[j], nums[i]nums[i], nums[right-1] = nums[right-1], nums[i]qsort(nums, left, i-1)qsort(nums, i+1, right)

快排的第二种实现：选择左边节点为主元，这样对于一个已经排好序的数组很不友好，因为划分之后也是只有一个区间。

def qsort(self, nums, left, right):if right - left < 1:return Nonepivot = nums[left]i = leftj = right+1while True:i += 1  # 遇到等于主元的就交换，如果直接略过，就令i=left+1,j=right,这个地方去掉就可以了j -= 1while i < j and nums[i] <= pivot:i += 1while nums[j] > pivot:j -= 1if i < j:nums[i], nums[j] = nums[j], nums[i]else:breaknums[left], nums[j] = nums[j], nums[left]self.qsort(nums, left, j-1)self.qsort(nums, j+1, right)

第二种解法：堆
可以直接建立小顶堆，在建立的过程中，一旦堆的元素个数大于k则删除堆顶元素。最终堆顶元素就是第k大的元素。
第一种方法：直接调用heapq

import heapq
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:n = len(nums)pq = []for i in range(n):heapq.heappush(pq,nums[i])if len(pq) > k:heapq.heappop(pq)return pq[0]

也可以先建立堆，然后利用nlargest直接获取最大的n个元素，然后输出第k个值。

import heapq
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:heap = heapq.heapify(nums)# nlargest返回结果为listreturn heapq.nlargest(k, nums)[k-1]

第二种方法：也可以直接使用大顶堆，出堆k-1次，此时堆顶元素即为第k大的元素。下面手撕一下大顶堆：

def build_maxHeap(nums) -> None:n = len(nums)for i in range(n // 2, 0, -1):adjust_down(nums, i)def adjust_down(nums: List[int], i) -> None:temp = nums[i]parent = iwhile parent * 2 <= len(nums) - 1:child = 2 * parentif child != len(nums) - 1 and nums[child + 1] > nums[child]:child += 1if nums[child] < temp:breakelse:nums[parent] = nums[child]parent = childnums[parent] = temp# 添加哨兵节点，便于后续操作        
nums = [float('inf')] + nums
build_maxHeap(nums)# 由于要寻找第k个最大的元素，所以每次我们都删除根节点，然后让最后一个位置的节点替换上来，然后再向下过滤即可，执行k-1次，此时根节点就是第k大的元素。
for i in range(1, k):nums[1] = nums[len(nums)-1]nums.pop(-1)adjust_down(nums, 1)
return nums[1]