Leetcode.有序矩阵中第 K 小的元素
2021/12/23 23:08:08
本文主要是介绍Leetcode.有序矩阵中第 K 小的元素,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给你一个 n x n
矩阵 matrix
,其中每行和每列元素均按升序排序,找到矩阵中第 k
小的元素。
请注意,它是 排序后 的第 k
小元素,而不是第 k
个 不同 的元素。
示例 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 · -10^9 <= matrix[i][j] <= 10^9 · 题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列 · 1 <= k <= n^2
解题思路:
- 找出二维矩阵中最小的数 left,最大的数 right,那么第 k 小的数必定在 left ~ right 之间
- mid=(left+right) / 2;在二维矩阵中寻找小于等于 midmid 的元素个数 count
- 若这个 count小于 k,表明第 k 小的数在右半部分且不包含 mid,即 left=mid+1, right=right,又保证了第 k 小的数在left ~ right之间
- 若这个 count大于 k,表明第 k 小的数在左半部分且可能包含 mid,即 left=left, right=mid,又保证了第 k 小的数在 left~right之间
- 因为每次循环中都保证了第 k 小的数在 left ~ right 之间,当 left==right 时,第 k 小的数即被找出,等于 right
解题代码:
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) >> 1); 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; int num = 0; while (i >= 0 && j < n) { if (matrix[i][j] <= mid) { num += i + 1; j++; } else { i--; } } return num >= k; } }
这篇关于Leetcode.有序矩阵中第 K 小的元素的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享