Keshawn_lu's Blog

Leetcode 378. 有序矩阵中第K小的元素

二分查找
字数统计: 708阅读时长: 3 min
2020/07/02 Share

题目简介：

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

1
2
3
4
5
6
7
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
返回 13。

提示：
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2。

思路：

利用二分查找，下界left为矩阵中数值最小的元素为左上角元素matrix[0][0]，上界right为最大的元素，即右下角元素matrix[matrix.size() - 1][matrix.size() - 1]。

将每次计算出来的mid与矩阵中的元素去比较，计算不大于mid的元素的数量。

由上图，取mid = 8 ，我们可以看到，矩阵中大于 mid 的数就和不大于 mid 的数分别形成了两个板块，沿着一条锯齿线将这个矩形分开。其中左上角板块的大小即为矩阵中不大于 mid 的数的数量。

我们只要沿着这条锯齿线走一遍即可计算出这两个板块的大小，也自然就统计出了这个矩阵中不大于 mid 的数的个数了。

走法演示如下，依然取 mid=8：

走法文字描述如下：

  • 初始位置为matrix[n - 1][0](左下角)。
  • 设当前位置为matrix[i][j]，若matrix[i][j] <= mid，那么第matrix[0 ... i][j]的值均小于mid，所以num += i + 1，并向右移动；否则向上移动(此时matrix[i][j] < mid)。
  • 不断移动直至走出边界。

统计矩阵中不大于mid的元素数量，若少于K，则说明答案x > mid，mid需要变大，即将left = mid + 1。

若不少于K，则说明答案x <= mid，将mid减少，即right = mid。(right = mid - 1会出错)

这样子，当while(left < right)条件不满足跳出循环时，所指的元素答案是唯一的，此时right == left，即区间里的元素只有一个。

最后返回left(或right)即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:

    int check(vector<vector<int>>& matrix, int k, int mid){

        int i = matrix.size() - 1;
        int j = 0;
        int num = 0;

        while(i >= 0 && j < matrix.size()){

            if(matrix[i][j] <= mid){

                num += i + 1;   //统计比mid小的元素数量
                j++;    //向右移动
            }else{

                i--;    //元素比mid大, 向上移动
            }
        }

        if(num < k)
            return 0;
        else
            return 1;
    }

    int kthSmallest(vector<vector<int>>& matrix, int k) {

        int n = matrix.size();
        int left = matrix[0][0];  //最小值
        int right = matrix[n - 1][n - 1]; //最大值

        while(left < right){    //left != right(同样效果)

            int mid = left + (right - left) / 2;

            if(check(matrix, k, mid) == 0)  //小于mid的值少于k, mid要变大
                left = mid + 1;
            else
                right = mid;    //小于mid的值大于等于k, mid要变小
        }

        return left;    //right也对

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网