leetcode-378:有序矩阵中第 K 小的元素

简介: leetcode-378:有序矩阵中第 K 小的元素

题目

题目连接

给你一个 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:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        vector<int> res;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++){
                res.push_back(matrix[i][j]);
            }
        }
        sort(res.begin(),res.end());
        return res[k-1];
    }
};

方法二:二分查找

参考链接

对于一个数mid,比它小的可以分为左上部分,比它大的可以分为右下部分,根据mid值,可以求出左上角的元素数量,可以跟k去比较。因此根据这个思路,可以进行二分查找,直接找值。

但是可能会有疑惑,left就一定在矩阵中吗?

是可以保证一定在的。 check(mid)是false,说明左上角数量比较少,因此mid+1,值是每次+1,第一次出现num==k的时候,此时left就一定是出现在矩阵里的

class Solution {
public:
    bool check(vector<vector<int>>& matrix,int mid,int k,int n){
        int i=n-1,j=0;
        int num=0;
        while(i>=0&&j<n){
            if(matrix[i][j]<=mid){
                num+=i+1;
                j++;
            }else{
                i--;
            }
        }
        return num>=k;
    }
    int kthSmallest(vector<vector<int>>& 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-left)/2;
            if(check(matrix,mid,k,n)){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
};
相关文章
|
1月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
34 1
|
1月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
32 0
|
1月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
29 0
|
1月前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
31 0
|
3月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
3月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer II 082. 含有重复元素集合的组合
解决LeetCode平台《剑指 Offer II 082. 含有重复元素集合的组合》题目的Python代码实现,通过深度优先搜索算法找出所有和为特定目标值的数字组合,并在搜索过程中通过排序和跳过重复元素来避免解集中出现重复组合。
40 2
|
3月前
|
算法
LeetCode第27题移除元素
这篇文章介绍了LeetCode第27题"移除元素"的解题方法,通过使用双指针技巧,有效移除数组中特定值的元素并返回新数组的长度。
|
3月前
|
算法 索引 Python
【Leetcode刷题Python】34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)
解决LeetCode "在排序数组中查找元素的第一个和最后一个位置" 问题的方法。第一种方法是使用两次二分查找,首先找到目标值的最左边界,然后找到最右边界。第二种方法是利用Python的list.index()方法,先正序找到起始位置,再逆序找到结束位置,并给出了两种方法的Python实现代码。
61 0
|
3月前
|
Python
【Leetcode刷题Python】203.移除链表元素
文章提供了三种删除链表中特定值节点的方法:迭代法、虚拟节点迭代删除法和递归法,并给出了相应的Python实现代码。
24 0