Leetcode #378. Kth Smallest Element in a Sorted Matrix

public int kthSmallest(int[][] matrix, int k) {
        int len = matrix.length;
        int low = matrix[0][0],high= matrix[len-1][len-1];
        while(low<=high){
            int mid = low + (high-low)/2;
            int count = helper(matrix,mid);
            if(count<k) low = mid+1;
            else high = mid-1; //排除mid不在矩阵内的情况,所以只能等到low和high时才退出循环
        }
        return low;
    }
    private static int helper(int[][] matrix, int mid) {
        // TODO Auto-generated method stub
        int i = matrix.length-1,j=0;
        int res = 0;
        while(i>=0&&j<matrix[0].length){
            if(matrix[i][j]>mid) i--;
            else{
                res+=i+1;
                j++;
            }
        }
        return res;
    }

根据二分搜索法,获取中间值,然后搜索他是否为第k个值。
主要中间值不在矩阵内的情况。这就是

if(count<k) low = mid+1;
            else high = mid-1;

这段语句的作用.

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一、基本数据类型 注释 单行注释:// 区域注释:/* */ 文档注释:/** */ 数值 对于byte类型而言...
    龙猫小爷阅读 9,724评论 0 16
  • 这两天在进行修行,虽然也学过很多次,但是每次只要到实操环节,就情不自禁泪流满面。 让我印象最深的是,...
    能量女王刘大红阅读 3,192评论 0 1
  • 继续说《大学》,昨天讲到“大学之道”,就是做一个顶天立地的大人的学问,儒家为此制定了三纲和八目。“纲”原指渔网上的...
    莲连阅读 2,732评论 0 1
  • 一名IT女,但是实在不喜欢自己的专业,想跨专业考研,但是不知道考什么专业。
    litterlight阅读 1,027评论 0 0
  • 2017-09-07摘抄自W3school-HTML CSS希望帮助自己系统地打好基础,也能在做笔记的同时添加一些...
    moralok阅读 1,111评论 0 0