q*m
2 楼
找k-1次predecessor? O(k)复杂度
【在 r*****e 的大作中提到】
: 问个问题啊。如何在杨氏矩阵中，高效的找到第k大的数或者第k小的数，没有没什么简
: 单的方法? 谢谢
【在 r*****e 的大作中提到】
: 问个问题啊。如何在杨氏矩阵中，高效的找到第k大的数或者第k小的数，没有没什么简
: 单的方法? 谢谢
g*y
3 楼
用一个min-heap。
刚开始min-heap里面是左上角的值。
每次动min-heap里面pop出一个最小值来，把这个最小值的右边和下边的值push到min-
heap里面去。
pop出来的第k个值就是最小值。
【在 r*****e 的大作中提到】
: 问个问题啊。如何在杨氏矩阵中，高效的找到第k大的数或者第k小的数，没有没什么简
: 单的方法? 谢谢
刚开始min-heap里面是左上角的值。
每次动min-heap里面pop出一个最小值来，把这个最小值的右边和下边的值push到min-
heap里面去。
pop出来的第k个值就是最小值。
【在 r*****e 的大作中提到】
: 问个问题啊。如何在杨氏矩阵中，高效的找到第k大的数或者第k小的数，没有没什么简
: 单的方法? 谢谢
r*e
4 楼
似乎不用min-heap? 只要保证矩阵的特性，每次只取左上角的A[0][0]。
我觉得还应改考虑到更新这个矩阵的时间，所以，O(K(M+N))
【在 g****y 的大作中提到】
: 用一个min-heap。
: 刚开始min-heap里面是左上角的值。
: 每次动min-heap里面pop出一个最小值来，把这个最小值的右边和下边的值push到min-
: heap里面去。
: pop出来的第k个值就是最小值。
我觉得还应改考虑到更新这个矩阵的时间，所以，O(K(M+N))
【在 g****y 的大作中提到】
: 用一个min-heap。
: 刚开始min-heap里面是左上角的值。
: 每次动min-heap里面pop出一个最小值来，把这个最小值的右边和下边的值push到min-
: heap里面去。
: pop出来的第k个值就是最小值。
g*y
5 楼
那还不如用min-heap呢。O(klogk)。
【在 r*****e 的大作中提到】
: 似乎不用min-heap? 只要保证矩阵的特性，每次只取左上角的A[0][0]。
: 我觉得还应改考虑到更新这个矩阵的时间，所以，O(K(M+N))
【在 r*****e 的大作中提到】
: 似乎不用min-heap? 只要保证矩阵的特性，每次只取左上角的A[0][0]。
: 我觉得还应改考虑到更新这个矩阵的时间，所以，O(K(M+N))
相关阅读
OPT 寄早了怎么办microsoft对从同类公司跳过去的experienced developer也要做哪些面经里的题目吗？贡献一次FEA职位技术面试题目 (转载)citi以及那几个大的银行还sponsor H1B吗Hitachi这句话是不是没绿卡就不用申请了的意思？新手问面试准备Jr PHP Developer Position转身份换语言学校需要什么理由去申请？ (转载)OPT期间可否出美国出差这次 InterviewStreet 的 Codesprint 被忽悠了，没几个公司可以申请的帮看看这段code有了解teach for america的吗出个题玩十万火急 求建议用Java去onsite Nvidia 会不会有硬伤？问道amazon面试题如何联系recuiter?通过linkedin可行吗h1b跳槽咨询使用PhD去申请一个要求最低是MS的职位合适吗？生物怀孕6个月onsite穿什么比较合适？ (转载)