题目来源

• leetcode：378. 有序矩阵中第 K 小的元素

题目描述

class Solution {
    
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
    

    }
};

题目解析

分析数据

（1）数据量。从下面可以看出：

• 这是一个正方形。
• 最大数据量： $300\ast 300=6\ast 10^4$
  • 算法复杂度不能是$O(N^2)$，因为会超过$10^8$
  • 至少应该是$O(N\ast logN)$
    

（2）数据特性

• 值域比较大，所以填表法pass
• 从左到右递增，从上往下递增，
  • 也就是它们具有单调性， 因此，思考：如何利用它呢？可不可以二分或者利用这个特性淘汰某些数据呢？
  • 另外，matrix[0][0]是最小值，matrix[n-1][n-1]是最大值。
• 从k的取值范围可以看出k可以找到矩阵中的任意一个数

二分（最优解）

思路

• 整个矩阵中最小的数是左上角的数(假设为1)，最大的数是右下角的数(假设为1000)。
• 第k小的数(假设k=100)一定在[1, 1000]之间。
• 怎么找这个k小的数呢？
  • 先找<= 500的数有几个？ 如果有200个，那么目标大了，因此
  • 再找<= 250的数有几个？如果有50个，那么目标小了，因此
  • 再找<=375的数有几个？如果刚好有100个，但是数组中并不一定有这个数，那么应该是<=375（>375的数一定会被淘汰）并且离它最近的那个数
• 因此，每一次二分都应该返回两个信息：
  • <= 某一个值的个数有几个？
  • 最接近它的是谁？

问题

思路：要求小于等于target的

• 尽量淘汰比target大的（列）
• 尽量保留小于等于target的（行）

从这里我们可以发现一个性质，

• 任取一个数x满足$l<=x<=r$，那么矩阵中不大于 midx 的数，肯定全部分布在矩阵的左上角。
• 例如下图，取 x=8：

问题

代码

复杂度： O((N + M) * log(max - min))

归并排序(使用堆)

思路

在整个矩阵中，每次弹出矩阵中最小的值，第k个被弹出的就是我们想要的数据

那么，每次弹出矩阵中最小的值呢？

当我们看到下面这个有序矩阵时，我们知道左上角的数字是整个矩阵最小的。

但是弹出它之后，如何能够保证接下来每一次都还能找到全矩阵中最小的值呢？

解决这个问题的关键，在于维护一组“最小值候选人”。

需要保证的是最小值必然从这组候选人中产生，于是每次只要从候选人中弹出一个最小的就可以了。

我们来选择第一组候选人，在这里可以选择第一列，因为每一个数字都是其对应行的最小值，全局最小必然在其中

第一次弹出很简单，将左上角的1弹出即可。

1弹出之后，我们如何找到下一个候选人呢？

很简单，刚才弹出的位置右移一格就行了，这样不是还能保证候选人链表中每一个数字都是每一行的最小值吗，那全局最小值必然在其中！

我们每次弹出候选人当中的最小值，然后把上次弹出候选人的右边一个补进来，就能一直保证全局最小值在候选人列表中产生，

···