题目难度：三星
考察点：二分

方法1：暴力、排序

1.分析：

其实这个题目我们完全可以以一种特别暴力的做法来做，就是直接输入n^2个数，然后将这n^2个数排序，输出第k个数就可以了，虽然也能过题，但是这样就不能理解这个题真正的做法了，所以这个方法仅仅适合笔试的时候。

2.复杂度分析：

时间复杂度：O(n^2log(n)) 
空间复杂度：O(n^2)

3.代码：  

#include <bits/stdc++.h>
using namespace std;
int main(){
    int k, n; cin>>k>>n;
    vector<int> a;
    for(int i=0; i<n*n; i++) {
        int x; cin>>x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    cout<<a[k-1]<<endl;
    return 0;
}


方法2：二分

1.分析：

我们重新分析一下题目，因为这个矩阵是行有序和列有序的，那么矩阵的左上角为最小元素l，右下角为最大元素r，显然我们要找的结果一定位于[l, r]这个区间内。那我们就可以利用二分来找到这个最终的结果。那么怎么二分呢？我们这样，利用m=(l+r)/2，那么我们此时计算矩阵中有多少个数小于等于m，如果小于等于m的个数小于k，那么显然当前的m是不符合条件的，所以结果肯定在[m+1,r]中；如果个数大于k的话，显然结果在[l, m]中，这样就达到二分的效果了，我们对其不断缩小搜索空间，直到个数=k的时候，输出即可。
那么现在问题来了，如何计算矩阵中小于等于m的个数呢？
我们一定要注意矩阵的特性，采用两个指针i=n-1, j=0, 表示从左下角开始遍历，如果满足if(a[i][j] > m)的话，那么显然m一定在i的上一层，即i--；否则一定在j的右边，j++，在此时记录小于m的个数，即ans+=(i+1)。
算法实现：
(1). 输入相应的数据
(2). 以l = a[0][0], r = a[n-1][n-1]  m = (l+r)>>1;进行二分
(3). 找到小于等于m的个数
(4). 输出二分得到的结果。

2.复杂度分析：

时间复杂度：O(nlog(n)) 
空间复杂度：O(n^2)

3.代码：  


#include <bits/stdc++.h>
using namespace std;
int main(){
    int k, n; cin>>k>>n;
    vector<vector<int>> a;
    for(int i=0; i<n; i++) {
        vector<int> v;
        for(int j=0; j<n; j++) {
            int x; cin>>x;
            v.push_back(x);
        }
        a.push_back(v);
    }
    int l = a[0][0], r = a[n-1][n-1];
    while(l < r) {
        int m = (l+r)>>1;
        int ll = n-1, rr = 0, sum = 0;
        while(ll>=0 && rr<n) {
            if(a[ll][rr] > m) ll--;
            else {
                sum += (ll+1);
                rr++;
            }
        }
        if(sum < k) l = m+1;
        else r = m;
    }
    cout<<l<<endl;
    return 0;
}