算法刷题Day1

BM47 寻找第k大

第一天就随便记录吧，万事开头难，我好不容易开的头，就别难为自己，去追求高质量了。嘿嘿嘿
题目传送门

解题思路一：维护一个大小为k的最小堆。最后返回堆顶元素。
代码：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param a int整型一维数组
# @param n int整型
# @param K int整型
# @return int整型
#
from heapq import heappushpop
from typing import List#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param a int整型一维数组
# @param n int整型
# @param K int整型
# @return int整型
#
from heapq import heappushpop
from typing import Listclass Solution:def findKth(self , a: List[int], n: int, K: int) -> int:# write code here# 维护一个大小为k的最小堆。最后返回堆顶元素import heapqheap = []# 将前k个数压进数组for i in range(K):heapq.heappush(heap, a[i])print(f"heap = {heap}")for i in range(K,n):# 取堆顶元素，如果堆顶元素小，poppush，如果堆顶元素一样，push。如果堆顶元素大，passheap_top = heap[0]print(f"{a[i], heap_top}")if a[i] > heap_top:heapq.heappop(heap)heapq.heappush(heap,a[i])elif a[i] == heap_top:heapq.heappush(heap,a[i])else:passprint(heap)return heap[-K]
so = Solution()
a,n,K = [10,10,9,9,8,7,5,6,4,3,4,2],12,3
print(so.findKth(a,n,K))