当前位置: 首页 > news >正文

算法刷题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)) 

解题思路二:二分查找,这个思路很值得学习
思路二 原帖传送门
等我实现实现

http://www.lryc.cn/news/495402.html

相关文章:

  • 泛化调用 :在没有接口的情况下进行RPC调用
  • Java 泛型详细解析
  • 题解:CF332B Maximum Absurdity
  • Vue 集成和使用 SQLite 的完整指东
  • 【JVM什么时候触发YoungGC和FullGC】
  • ubuntu配置网络
  • 第十一课 Unity编辑器创建的资源优化_预制体和材质篇(Prefabs和Materials)详解
  • 2024.11.29(单链表)
  • 基于深度学习和卷积神经网络的乳腺癌影像自动化诊断系统(PyQt5界面+数据集+训练代码)
  • opengl 三角形
  • 23种设计模式-抽象工厂(Abstract Factory)设计模式
  • 手机上怎么拍证件照,操作简单且尺寸颜色标准的方法
  • IDEA报错: java: JPS incremental annotation processing is disabled 解决
  • OCR实现微信截图改名
  • 第一届“吾杯”网络安全技能大赛 Writeup
  • 再谈Java中的String类型是否相同的判断方法
  • <一>51单片机环境
  • 【0x0001】HCI_Set_Event_Mask详解
  • 第三方Express 路由和路由中间件
  • 七、Python —— 元组、集合和字典
  • Aes加解密
  • 【时时三省】Tessy 故障入侵 使用教程
  • .NET 9 AOT的突破 - 支持老旧Win7与XP环境
  • CondaValueError: Malformed version string ‘~‘: invalid character(s).
  • 01-Ubuntu24.04LTS上安装PGSQL
  • Esp32使用micropython基于espnow实现语音对讲机
  • Docker 容器隔离关键技术:SELinux
  • Java并发07之ThreadLocal
  • 【单细胞数据库】癌症单细胞数据库CancerSEA
  • Rsa加解密 + 签名验签