LEETCODE 378 有序矩阵中第K小的元素

378. 有序矩阵中第K小的元素

1.二分法

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        auto n=matrix.size();
        int l=matrix[0][0],r=matrix[n-1][n-1];
        while(l<r)
        {
            int mi=l+(r-l)/2;
            if(check(matrix,mi,k,n))
                r=mi;
            else
                l=mi+1;
        }
        return l;
    }
    bool check(vector<vector<int>>& v,int mid,int k,int n)
    {
        int x=n-1,y=0,cnt=0;
        while(x>=0&&y<n)
        {
            if(v[x][y]<=mid)
            {
                cnt+=(x+1);
                ++y;
            }
            else
                --x;
        }
        return cnt>=k;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2. 优先级队列

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
    struct point
    {
        point(int val,int xx,int yy):v(val),x(xx),y(yy)
        {  
        }
        bool operator> (const point& r)const 
        {
            return v>r.v;
        }
        int v;
        int x;
        int y;
        
    };
        int n=matrix.size();
        priority_queue<point,vector<point>,greater<point>>p;
        for(int i=0;i<n;++i)
        {
            p.emplace(matrix[i][0],i,0);
        }
        for(int i=1;i<k;++i)
        {
            auto tmp=p.top();
            p.pop();
            if(tmp.y<n-1)
            {
                p.emplace(matrix[tmp.x][tmp.y+1],tmp.x,tmp.y+1);
            }
        }
        return p.top().v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

总结：

1. 一般求第K大的数这种TOP k问题，可以考虑使用优先级队列，这道题里为了找到我们删除堆顶元素后的下一个元素，定义了一个point类辅助,如果是求n个链表的第k个数，那么就可以直接用堆保存链表节点。
2. 有序数组的相关问题考虑用二分法，难点在于找到二分法中的判断条件，本题中的check()函数。