r*****e
发帖数: 146 | 1 问个问题啊。如何在杨氏矩阵中，高效的找到第k大的数或者第k小的数，没有没什么简
单的方法? 谢谢 |
q****m
发帖数: 177 | 2 找k-1次predecessor? O(k)复杂度
【在 r*****e 的大作中提到】
: 问个问题啊。如何在杨氏矩阵中，高效的找到第k大的数或者第k小的数，没有没什么简
: 单的方法? 谢谢
|
g****y
发帖数: 240 | 3 用一个min-heap。
刚开始min-heap里面是左上角的值。
每次动min-heap里面pop出一个最小值来，把这个最小值的右边和下边的值push到min-
heap里面去。
pop出来的第k个值就是最小值。
【在 r*****e 的大作中提到】
: 问个问题啊。如何在杨氏矩阵中，高效的找到第k大的数或者第k小的数，没有没什么简
: 单的方法? 谢谢
|
r*****e
发帖数: 146 | 4 似乎不用min-heap? 只要保证矩阵的特性，每次只取左上角的A[0][0]。
我觉得还应改考虑到更新这个矩阵的时间，所以，O(K(M+N))
【在 g****y 的大作中提到】
: 用一个min-heap。
: 刚开始min-heap里面是左上角的值。
: 每次动min-heap里面pop出一个最小值来，把这个最小值的右边和下边的值push到min-
: heap里面去。
: pop出来的第k个值就是最小值。
|
g****y
发帖数: 240 | 5 那还不如用min-heap呢。O(klogk)。
【在 r*****e 的大作中提到】
: 似乎不用min-heap? 只要保证矩阵的特性，每次只取左上角的A[0][0]。
: 我觉得还应改考虑到更新这个矩阵的时间，所以，O(K(M+N))
|
