最直接的办法就是给整个矩阵排序,然后找第K大的数。复杂度是(O(n^2logk))。其实还有更快的办法。 假设行列都是增序。注意到在矩阵的对角线上中任选一点x,右下角的矩阵里面的数都大于或等于x,而这里包含了(x^2)个数。因此,必然可以找到一个位置x,使得 ((x+1)^2\leq n-k\leq x^2) 。 这样K就在 M(x+1, x+1) .. M(x+1, n) 和 M(x+1, x+1) .. M(n, x+1) 以及 x 这三个范围内。 对这个范围内的数字排序,找第K个数字,复杂度是 (O(nlogk))