二叉树 查找第k大的数
2022/8/20 23:56:58
本文主要是介绍二叉树 查找第k大的数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
改造方法
需在节点N中记录以节点N为根的子树的节点数numOfNodes,
根节点记录整颗树的节点数目,
则若根节点的左子树的numOfNodes刚好为k-1,那这个根节点的值即为目标值。
注意递归时,k需变化,因为有可能在右子树上
使用二叉堆
法一
将数组构建成一个二叉堆(这时要求最大的在上面),
然后执行k次删除最小元,则最后一次删除得到的数即为第k大的数
法二
仅构建一个大小为K的堆(最小的在上面)
堆满后,每次只添加比根更大的元素,则结束后 堆顶元素即为第K大的数
这篇关于二叉树 查找第k大的数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行