LeetCode_二分搜索_中等_378. 有序矩阵中第 K 小的元素
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) 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了,但是你会发现阅读这篇文章()很有趣。
2.思路
(1)排序(时空复杂度不符合题目要求) 比较容易想到的方法是先将矩阵转换为一维数组,然后再对一维数组进行排序,最后直接返回一维数组中的第 k 小元素即可。不过该方法的时间复杂度为 O(n2logn),空间复杂度为 O(n2),不符合题目要求。
(2)二分搜索 思路参考。
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; } }
上一篇:
IDEA上Java项目控制台中文乱码