作者:手机用户2602913361 | 来源:互联网 | 2023-06-02 11:20
首先看到第k大,想到堆,求第k大,用最小堆然后我们要维护这个堆,具体怎么维护这个堆里面的值是前k大的呢?从矩阵的最右下角开始,把这个右下角的值进入一个优先队列,然后出队,出来的这个
首先看到第k大,想到堆,求第k大,用最小堆
然后我们要维护这个堆,具体怎么维护这个堆里面的值是前k大的呢?
从矩阵的最右下角开始,把这个右下角的值进入一个优先队列,然后出队,出来的这个元素的值就是最大的,然后把这个元素的左边和上边的元素都压进队列,这样可以保证每次优先队列选取的都是当前矩阵中最大的值。当出队k次后,最后一个出队的就是第k大。复杂度klogk
第二种思路:
二分法。
矩阵种最小的元素是m[0][0],最大的是m[n-1][n-1]
二分答案,看矩阵中有多少个元素比当前的元素大。