LeetCode_二分搜索_中等_378. 有序矩阵中第 K 小的元素

素颜马尾好姑娘i 2023-10-06 22:57 16阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

**示例 1：**  
输入：matrix = \[\[1,5,9\],\[10,11,13\],\[12,13,15\]\], k = 8  
输出：13  
解释：矩阵中的元素为 \[1,5,9,10,11,12,13,13,15\]，第 8 小元素是 13

**示例 2：**  
输入：matrix = \[\[-5\]\], k = 1  
输出：-5

**提示：**  
n == matrix.length  
n == matrix\[i\].length  
1 <= n <= 300  
\-109 <= matrix\[i\]\[j\] <= 109  
题目数据保证 matrix 中的所有行和列都按非递减顺序排列  
1 <= k <= n2

**进阶：**  
你能否用一个恒定的内存（即 O(1) 内存复杂度）来解决这个问题?  
你能在 O(n) 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（[this paper][]）很有趣。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix

## 2.思路 ##

（1）排序（时空复杂度不符合题目要求）  
比较容易想到的方法是**先将矩阵转换为一维数组，然后再对一维数组进行排序，最后直接返回一维数组中的第 k 小元素即可**。不过该方法的时间复杂度为 O(n2logn)，空间复杂度为 O(n2)，不符合题目要求。

（2）二分搜索  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————排序（时空复杂度不符合题目要求）
    class Solution {
        
        public int kthSmallest(int[][] matrix, int k) {
        
            int rows = matrix.length;
            int cols = matrix[0].length;
            int[] sortedNums = new int[rows * cols];
            int index = 0;
            //将二维数组转换为一维数组
            for (int[] row : matrix) {
        
                for (int num : row) {
        
                    sortedNums[index++] = num;
                }
            }
            //对一维数组 sortedNums 进行排序
            Arrays.sort(sortedNums);
            //返回一维数组中的第 k 小元素
            return sortedNums[k - 1];
        }
    }

//思路2————二分搜索
    class Solution {
        
        public int kthSmallest(int[][] matrix, int k) {
        
            int n = matrix.length;
            int left = matrix[0][0];
            int right = matrix[n - 1][n - 1];
            while (left < right) {
        
                int mid = left + ((right - left) / 2);
                if (check(matrix, mid, k, n)) {
        
                    right = mid;
                } else {
        
                    left = mid + 1;
                }
            }
            return left;
        }
        
        public boolean check(int[][] matrix, int mid, int k, int n) {
        
            int i = n - 1;
            int j = 0;
            // num 为矩阵中小于等于 mid 的元素的个数，初始值为 0
            int num = 0;
            while (i >= 0 && j < n) {
        
                if (matrix[i][j] <= mid) {
        
                    num += i + 1;
                    j++;
                } else {
        
                    i--;
                }
            }
            return num >= k;
        }
    }

[this paper]: http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf
[Link 1]: https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/solution/you-xu-ju-zhen-zhong-di-kxiao-de-yuan-su-by-leetco/