【Leetcode】378. Kth Smallest Element in a Sorted Matrix（第k个大的数）（容器）

灰太狼 2021-12-09 06:33 147阅读 0赞

Given a *n* x *n* matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

**Example:**

matrix = [
       [ 1,  5,  9],
       [10, 11, 13],
       [12, 13, 15]
    ],
    k = 8,
    
    return 13.

**Note:**   
You may assume k is always valid, 1 ≤ k ≤ n2.

题目大意：

给出一个矩阵，矩阵中的每一行和每一列都是已经排序好的，我们需要按照找出这个矩阵当中第k个大的数。

解题思路：

看讨论区里直接将矩阵转化成为一维数组排序出结果，貌似比搜索还要快。

最后想练习一下容器。利用priority\_queue来排序pair，每个比当前大的数可能出现在右面或者下面。

class Solution {
    private:
        int map_x[2] = {1,0};
        int map_y[2] = {0,1};
        bool valid(int x, int y, int n){
            if(x>=0 && x<n && y>=0 && y<n){
                return true;
            }
            return false;
        }
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            if(k==1) return matrix[0][0];
            int n = matrix.size();
            bool maps[n][n];
            memset(maps, false, sizeof(maps));
            priority_queue<pair<int, vector<int>>, vector<pair<int, vector<int>>>, greater<pair<int, vector<int>>> > q;
            vector<int> tmp_v;
            tmp_v.push_back(0);
            tmp_v.push_back(0);
            pair<int ,vector<int>> p1;
            p1.first = matrix[0][0];
            p1.second = tmp_v;
            q.push(p1);
            maps[0][0]= true;
            int ans = matrix[0][0];
            while(k--){
                int x = q.top().second[0];
                int y = q.top().second[1];
                ans = q.top().first;
                q.pop();
                for(int k = 0;k<2;k++){
                    int cor_x = map_x[k] + x;
                    int cor_y = map_y[k] + y;
                    if(valid(cor_x, cor_y,n) && maps[cor_x][cor_y]==false){
                        maps[cor_x][cor_y] = true;
                        vector<int> tmp_v;
                        tmp_v.push_back(cor_x);
                        tmp_v.push_back(cor_y);
                        pair<int ,vector<int>> p1;
                        p1.first = matrix[cor_x][cor_y];
                        p1.second = tmp_v;
                        q.push(p1);
                    }
                } 
            }
            return ans;
        }
    };