文章目录
1. 题目2. 解题2.1 暴力法2.2 二分查找
1. 题目
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。 请注意，它是排序后的第k小元素，而不是第k个元素。
示例
:
matrix
= [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k
= 8,
返回
13。
说明
:
你可以假设 k 的值永远是有效的
, 1 ≤ k ≤ n
^2 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 暴力法
将所有元素插入小顶堆然后出队k-1个，最后的堆顶就是答案，时间复杂度 O(n
2)
class Solution {
public:
int kthSmallest(vector
<vector
<int>>& matrix
, int k
) {
priority_queue
<int,vector
<int>,greater
<int>> q
;
for(auto row
: matrix
)
for(auto elem
: row
)
q
.push(elem
);
while(--k
)
q
.pop();
return q
.top();
}
};
2.2 二分查找
找出矩阵中最小数left，最大数right，第k小的数在left~right之间mid=(left+right) / 2；在矩阵中寻找小于等于mid的元素个数count若count<k，第k小的数在右半部分且不包含mid，即left=mid+1, right=right若count>=k，第k小的数在左半部分且可能包含mid，即left=left, right=mid当left==right时，第k小的数即被找出
class Solution {
public:
int kthSmallest(vector
<vector
<int>>& m
, int k
) {
int r
= m
.size(), c
= m
[0].size();
int left
= m
[0][0], right
= m
[r
-1][c
-1], mid
, count
;
while(left
< right
)
{
mid
= left
+((right
-left
)>>1);
count
= findNotBigerThanMid(m
,mid
,r
,c
);
if(count
< k
)
left
= mid
+1;
else
right
= mid
;
}
return left
;
}
int findNotBigerThanMid(vector
<vector
<int>> &m
, int &mid
, int &r
, int &c
)
{
int i
= r
-1, j
= 0, count
= 0;
while(i
>= 0 && j
< c
)
{
if(m
[i
][j
] <= mid
)
{
count
+= i
+1;
j
++;
}
else
i
--;
}
return count
;
}
};
上面的辅助求count函数，还可写成
int findNotBigerThanMid(vector
<vector
<int>> &m
, int &mid
, int &r
, int &c
)
{
int i
= 0, j
= c
-1, count
= 0;
while(i
< r
&& j
>= 0)
{
if(m
[i
][j
] <= mid
)
{
count
+= j
+1;
i
++;
}
else
j
--;
}
return count
;
}
参考 Leetcode 240 搜索二维矩阵 II
