sorted matrix - search & find-k-th
sorted matrix ( Young Matrix )
search for a given value in the matrix:
1) starting from upper-right corner, turn left or turn down, O(n+m)
2) if it's square, O(n+m) is optimal, see http://stackoverflow.com/a/10597806
3) if it's not square, e.g. in extreme case it degenerates to a sorted array, the complexity is lower-bounded to O(m*(1+log(n/m)) (suppose m < n)
4) page http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster has more details
find k-th element in the matrix: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
a) heap-based, starting from top-left corner element, push to heap; each time an element is poped, push its right and down elements.
complexity is k*log(k)
b) binary-search on target value, starting from [smallest, largest], and then count how many elements are less than this value to see if it's kth element. O(n*log(n)*log(N)) where n is number of rows, N is (largest-smallest)
最新文章
- 【WPF系列】基础学习-WPF架构概览
- HD1556Color the ball（树状数组）
- 【转】GATK使用方法详解（包含bwa使用）
- Nagios Looking Glass 本地文件包含漏洞
- Colors
- zabbix 编译
- this、new、apply和call详解
- Android开发中在一个Activity中关闭另一个Activity
- Javascript:DOM表格操作
- 2013 南京邀请赛 C count the carries
- 证明N={1，2，...，n，...}最高万元 黄晓宁
- MOBA战斗服务器设计思路
- [Python Study Notes]with的使用
- OkHttp的封装和使用详解
- Python全栈开发记录_第二篇（文件操作及三级菜单栏增删改查）
- 不要拿ERP的报表忽悠领导！——一个报表引发的企业经营反思
- php+mysql注入
- **CI中创建你自己的类库
- 关系型数据库MySQL主从同步-读写分离
- Paint、Canvas、Matrix使用解说(一、Paint)