wap网站软件,做一个网站要注意什么,增城高端网站建设,织梦cms做企业网站给你一个 n x n 矩阵 matrix #xff0c;其中每行和每列元素均按升序排序#xff0c;找到矩阵中第 k 小的元素。 请注意#xff0c;它是 排序后 的第 k 小元素#xff0c;而不是第 k 个 不同 的元素。
你必须找到一个内存复杂度优于 O(n2) 的解决方案。
示例 1#xff1…给你一个 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
二分
class Solution {
public:bool check(vectorvectorint 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 k num;}int kthSmallest(vectorvectorint matrix, int k) {int n matrix.size();int left matrix[0][0];int right matrix[n-1][n-1];while(left right){int mid (left right) 1;if(check(matrix, mid, k, n)){right mid;}else{left mid 1;}}return left;}
};时间复杂度O(nlog(r−l))二分查找进行次数为 O(log(r−l))每次操作时间复杂度为 O(n)。 空间复杂度O(1)。 矩阵中最小的元素是matrix[0][0]最大的元素是matrix[n-1][n-1]这道题使用二分查找的思想就是我们从最小数到最大数之间任意挑一个数字作为mid。假设mid 8根据图片矩阵可以分成两个部分一个部分全部小于等于8另外一个部分全部大于8。我们可以统计左上部分小于等于8的数的数量看8在排序后是第几小的数因为图片有多个8所以返回的是8是第几小的数的最大情况即升序排列中最右边的8的位置。
所以在二分查找中我们从取left right除以2的值为mid如果在check函数中得出来左上部分的数量大于等于我们所期待的k那么就说明我们的取的mid大于等于实际元素这时候我们就将right mid缩小他的上界。如果左上部分数量小于我们所期待的k说明我们取的mid比实际元素要小我们令left mid 1增加他的下界。
很多人会疑问left怎么确保一定是矩阵中的数
如题解中所说如果 num k那么说明最终答案 x mid如果 num k那么说明最终答案 x mid。 在最后一次迭代时check返回的结果为false即 num k说明 x mid又因为 x right。当 left mid 1 后left righwhile循环结束。此时有 mid x right left mid 1即 mid x mid 1。可得 x mid 1 left。
