LeetCode_二分搜索_中等_378. 有序矩阵中第 K 小的元素
2023-09-27 14:25:46 时间
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)二分搜索
思路参考本题官方题解。
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;
}
}
相关文章
- Leetcode: Sparse Matrix Multiplication
- leetcode 二分法 Pow(x, n)
- 【Leetcode】143. 重排链表(中等)
- JS Leetcode 1370. 上升下降字符串 题解分析,桶排序与charCodeAt fromCharCode妙用
- [LeetCode] Sort Colors
- 111、【树与二叉树】leetcode ——669. 修剪二叉搜索树:递归法(C++版本)
- 109、【树与二叉树】leetcode ——701. 二叉搜索树中的插入操作:递归法+双指针迭代法(C++版本)
- 104、【树与二叉树】leetcode ——98. 验证二叉搜索树:递归法[先序+中序+后序]+迭代法(C++版本)
- 【LeetCode】11. Container With Most Water
- 【LeetCode】164. Maximum Gap (2 solutions)
- 【leetcode】538/1038: 把二叉搜索树转化为累加树
- [LeetCode] 1268. Search Suggestions System 搜索推荐系统
- [LeetCode] Prefix and Suffix Search 前后缀搜索
- [LeetCode] Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树
- [LeetCode] Longest Line of Consecutive One in Matrix 矩阵中最长的连续1
- [LeetCode] 450. Delete Node in a BST 删除二叉搜索树中的节点
- [LeetCode] Department Top Three Salaries 系里前三高薪水
- [LeetCode] 333. Largest BST Subtree 最大的二分搜索子树
- [LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最小共同父节点
- [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二
- [LeetCode] 96. Unique Binary Search Trees 独一无二的二叉搜索树
- 动态规划TLE之后转向单调栈的解题路径——LeetCode 84 柱状图中的最大矩形(困难)