[LeetCode] 378、有序矩阵中第K小的元素

10 阅读 作者:aift 2020-05-11

题目描述

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

示例:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13

解题思路

和《剑指offer》第4题类似,但是不一样。其实这个题的“二分法”的思路跟《剑指offer》的面试题3的题目二思路更像。

  • 二分法

    • 找出二维矩阵中最小的数left,最大的数right,那么第k小的数必定在left~right之间。
    • mid=(left+right) / 2;在二维矩阵中寻找小于等于mid的元素个数count。
    • 若这个count小于k,表明第k小的数在右半部分且不包含mid,即left=mid+1, right=right,又保证了第k小的数在left~right之间。
    • 若这个count大于k,表明第k小的数在左半部分且可能包含mid,即left=left, right=mid,又保证了第k小的数在left~right之间。
    • 因为每次循环中都保证了第k小的数在left~right之间,当left==right时,第k小的数即被找出,等于right。

    注:这里的left mid right是数值,不是索引位置。

参考代码

typedef long long LL;
class Solution
{
public:
    int kthSmallest(vector<vector<int>>& matrix, int k){
        int rows = matrix.size();
        int cols = matrix[0].size();
        LL left = matrix[0][0];
        LL right = matrix[rows-1][cols-1];

        while(left < right){
            // 每次循环都保证第K小的数在left~right之间,当left==right,第k小的数就是left
            LL mid = (left + right) >> 1;
            // 找二维矩阵中<=mid的元素总个数
            LL cnt = findNotBiggerThanMid(matrix, rows, cols, mid);
            
            if(cnt < k)
                // 第k小的数在右半部分,且不包含mid
                left = mid + 1;
            else
                // 第k小的数在左半部分,可能包含mid
                right = mid;
        }
        
        return left;
    }
	
	// 根据有序矩阵的性质,优化查找过程
    int findNotBiggerThanMid(vector<vector<int>>& matrix, int rows, int cols, int mid){
    	// 从左下角开始找
        int i = rows - 1;
        int j = 0;
        int cnt = 0;
        while(i >= 0 && j < cols){
            if(matrix[i][j] <= mid){
                // 第j列有i+1个元素<=mid
                cnt += (i+1);
                j++;
            }
            else{
                // 第i行目前的数大于mid,需要继续在当前列往上找
                i--;
            }
        }

        return cnt;
    }
    
};

最大堆

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        priority_queue<int> pq;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                pq.push(matrix[i][j]);
                if (pq.size() > k) pq.pop();
            }
        }
        return pq.top();
    }
};
原文地址:https://blog.csdn.net/ft_sunshine/article/details/103546595
广告一下
热门教程
PHP7报A non well formed numeric value encountered 0
Linux系统下关闭mongodb的几种命令分享 0
mongodb删除数据、删除集合、删除数据库的命令 0
Git&Github极速入门与攻坚实战课程 0
python爬虫教程使用Django和scrapy实现 0
libnetsnmpmibs.so.31: cannot open shared object file 0
数据结构和算法视频教程 0
redis的hash结构怎么删除数据呢? 0
C++和LUA解析器的数据交互实战视频 0
mongodb errmsg" : "too many users are authenticated 0
C++基础入门视频教程 0
用30个小时精通C++视频教程可能吗? 0
C++分布式多线程游戏服务器开发视频教程socket tcp boost库 0
C++培训教程就业班教程 0
layui的util工具格式时间戳为字符串 0
C++实战教程之远程桌面远程控制实战 1
网络安全培训视频教程 0
LINUX_C++软件工程师视频教程高级项目实战 0
C++高级数据结构与算法视频教程 0
跨域问题很头疼?通过配置nginx轻松解决ajax跨域问题 0
相关文章
【译】JavaScript数据结构(3):单向链表与双向链表 16
10个JavaScript难点 16
【译】苹果拒绝支持PWA,有损Web的未来 16
iView 一周年了,同时发布了 2.0 正式版,但这只是开始... 16
nodejs+mongodb构建一个简单登录注册功能 16
【译】JavaScript数据结构(4):树 16
组件化开发与黑箱 16
TypeScript - 不止稳,而且快 16
webpack3+anujs+ReactCSSTransitionGroup 16
原生js实现图片放大镜效果 16
WEB缓存探究第二弹——实战 16
纯笔记:vfork 的一些使用场景(顺便讲一下 fork 的原理) 16
Android APP 内部捐赠实现(支付宝&amp;微信) 16
WKWebView 的一些小总结 16
模型评价(一) AUC大法 16
开始使用GraphQL 16
Webpack模块化原理简析 16
gulp使用问题记录 16
使用Angular4动画为页面添彩 16
Python27 Matplotlib (win64 python2.7) 安装及简单使用 16