行列有序矩阵求第k大元素
2024-10-19 01:59:29
问题来源:http://www.careercup.com/question?id=6335704
问题描述:
Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.
解答:
先给出算法的时空复杂度,时间O(k * lg k),空间O(k)。
算法:为了方便描述不防假设矩阵左上角的元素最小,且k<=n。
1. 取每行行首元素建立规模为k的最小堆。
2. 删除堆顶元素,同时将该元素所在行的下一个元素插入最小堆
3. 循环步骤2,k次即可获得所需元素
复杂性分析: 第一步建堆时间为O(k * lg k). 第二三步插入删除堆顶元素k次,时间复杂度O(k * lg k).总的复杂度为O(k * lg k).
正确性分析:
每次确保删除的元素是整个矩阵中的当前最小元素,故而保证了准确性。
个人感觉:
算法还有待修改,毕竟这样找到的是前k大而不仅仅是第k大,做了许多无用功。
最新文章
- php判断是否是微信客户端的浏览器访问
- soap缓存问题
- ACL权限的学习
- 【LCS,LIS】最长公共子序列、单调递增最长子序列
- Unity3d shader内置矩阵
- 【转】QT样式表 (QStyleSheet)
- Ubuntu上用mod_wsgi部署Django出现的一些问题
- SQL SERVER 判断是否存在并删除某个数据库、表、视图、触发器、储存过程、函数
- Android Acitivy切换平移动画效果实现
- MySQL 复制 - 性能与扩展性的基石 2:部署及其配置
- MATLAB accumarray
- firefox support.mozilla.org 的管理员没有正确配置好此网站。为避免您的信息失窃,Firefox 并未与此网站建立连接。
- meterpreter 渗透用法
- leetcode102
- mysql 安装目录说明
- [osg]OSG相机添加动画路径
- android-------开发常用框架汇总
- Rabbitmq基本原理(转)
- Springboot学习笔记(七)-集成Redis
- 大圣画廊v0.2(2015.7.17)