有序矩阵中第K小的元素
有序矩阵中第K小的元素
https://www.nowcoder.com/practice/07b66536f3f94f88908fe598108172d5?tpId=98&tqId=32883&tPage=3&rp=3&ru=%2Fta%2F2019test&qru=%2Fta%2F2019test%2Fquestion-ranking
题目难度：三星
考察点：二分
方法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;
}
