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

乔戈里

发布于 2019-09-17 13:43:22

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个元素。

示例:

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

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

暴力解决

思路

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

代码

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];
    }
}

二分解决

思路

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

代码

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;
    }
}

代码讲解

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

结束语

2018.11.1打卡~

END

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2018-11-01，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法