验证中...
私信发送成功
在一个排序矩阵中(每行没列都有序),找到第k小的数。
原始数据 复制代码
/*
问题:
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
Note: You may assume k is always valid, 1 ≤ k ≤ n2.
*/
/*
解答:
1.该题为二分查找的应用。
2.38-41行,对当count==k情况的处理,一定是max=mid。因为当count==k时,mid可能就是寻找的值或者比寻找的值大
一点(mid在第k小和第k+1小的数之间),所以下一次缩小范围时,一定要把mid包括进去,否可能错过寻找的数。
*/
class Solution
{
public:
int kthSmallest(vector<vector<int>>& matrix, int k)
{
int min, max, mid, count;
int i, pos;
min = matrix[0][0];
max = matrix[matrix.size()-1][matrix.size()-1];
while(min < max)
{
count = 0;
mid = (min + max) / 2;
for(i=0; i<matrix.size(); i++)
{
pos = upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
count += pos;
}
if(count < k)
min = mid + 1;
else
max = mid;
}
return min;
}
};

评论列表( 0 )

你可以在登录后,对此项目发表评论

4_float_left_people 4_float_left_close