前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每天一道leetcode378-有序矩阵中第K小的元素

每天一道leetcode378-有序矩阵中第K小的元素

作者头像
乔戈里
发布2019-09-17 13:43:22
1.1K0
发布2019-09-17 13:43:22
举报
文章被收录于专栏:Java那些事

题目

leetcode378-有序矩阵中第K小的元素

英文链接:

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

中文链接:

https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/

分类:二分查找类

题目详述

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

示例:

代码语言:javascript
复制
matrix = [
[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,返回 13。

说明: 你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

暴力解决

思路

  1. 额,看到这个题目,一开始大体思路就是暴力解决;
  2. 遍历整个二维数组,然后把这个二维数组存到一个一维数组中,然后对这个一维数组,进行排序,然后取这个一维数组第k个值就行。

代码

代码语言:javascript
复制
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        if(matrix.length == 0 || matrix[0].length == 0)
            return -1;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int number = rows * cols;
        int [] list = new int[number];
        int count = 0;
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                list[count] = matrix[i][j];
                count++;
            }
        }
        Arrays.sort(list);
        return list[k-1];
    }
}

二分解决

思路

  1. 由于是一个矩阵,左上角的数是最小值,右下角的数是最大值,所以可以利用这一个特点来进行二分,每次取两个边界的值进行除以2,得到一个mid值;
  2. 然后根据这个mid值,统计整个矩阵中,小于mid值的个数,如果小于mid的值的个数刚好大于等于k个,那么说明应该缩小right的值到mid,如果小于k个,那么说明left应该变成mid;
  3. 这样一步步进行紧逼,找到最后的这个数据。

代码

代码语言:javascript
复制
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0], right = matrix[n - 1][n - 1];
        while (left + 1 < right) {
            int mid = (right - left) / 2 + left;
            int num = count(matrix, mid);
            if (num >= k) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (count(matrix, right) <= k - 1) return right;
        return left;
    }
    public int count(int[][] matrix, int target) {
        int n = matrix.length;
        int i = n - 1, j = 0;
        int res = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] < target) {
                res += i + 1; //index + 1 = number of elements.
                j++;
            } else {
                i--;
            }
        }
        return res;
    }
}

代码讲解

  1. 17行到30行代码就是求矩阵中小于target的数的大小,这里的话从第0列开始的最底层开始找,如果左下角的数比target小,那么说明这一列的数都是小于target所以,也就是出现了代码22行到24行,因为这个一列已经找过了,所以j++,移动到下一列去找;
  2. 如果左下角的数比target大,由于每一行递增,所以只能是i--,来去找下一行;以上就是对17行-30行代码的讲解
  3. 题目中使用了二分查找,去找最小值和最大值的中间值,如果小于中间值的个数是k个或者大于k个,那么让right去等于mid,往左边逼近;
  4. 如果小于中间值mid的个数是小于k的,那么说明不够k个,也就只能取把left变大,等于mid;
  5. 然后循环结束的条件是left+1<right;说明这时候结束的时候已经是left与right无限逼近了,这个时候left与right的中间值在数组里面(这里我也没有数学证明,left与right一直求中间值,那么最后中间值mid一定在数组里面???这个我自己试验了几个数组,确实是这样子,但是我数学能力有限,无法去证明,有人能证明吗,欢迎评论区留言

结束语

2018.11.1打卡~

END

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-11-01,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员乔戈里 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档