三个月算法进阶--day39
目录
最大值堆、最小值堆
维护动态数据的最大最小值，考虑堆
第K个最大元素，建立容量为K的最小值堆，堆顶的元素为所求
只用k个容量的优先队列，而不用全部len个容量
动态数据流
最大优先队列、最小优先队列
优先出队
优先队列的入队和出队时间复杂度是logn
二叉堆结点的上浮和下沉
记录
leetcode第215题数组中的第K个最大元素
暴力解法
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums.sort(reverse=True)
return nums[k-1]
堆
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
import heapq
return heapq.nlargest(k, nums)[-1]
小顶堆求最大值
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
import heapq
nums = [-num for num in nums]
heapq.heapify(nums)
for _ in range(k):
res = heapq.heappop(nums)
return -res
优先队列
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
from queue import PriorityQueue as PQ
pq = PQ()
for i, t in enumerate(nums):
if i < k:
pq.put(t)
continue
tmp = pq.get()
if tmp > t:
pq.put(tmp)
else:
pq.put(t)
return pq.get()
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
from queue import PriorityQueue as PQ
pq = PQ()
for i, t in enumerate(nums):
if i < k:
pq.put(t)
continue
pq.put(t)
pq.get()
return pq.get()